C++ での再帰的フィボナッチ

この小さなチュートリアルでは、C++ で再帰関数を使用してフィボナッチ数列を実装する方法について説明します。 そのために、最初に再帰関数について簡単に紹介します。

C++ の再帰関数

再帰関数はそれ自身の本体内でそれ自体を呼び出します。この概念を使用することを再帰と呼びます。 この概念は多くの点で役に立ち、一部の関数は再帰のみを使用して実装できます。

上の図は、再帰の概念を示しています。 main 関数で関数 recurse が呼び出され、その関数で recurse が再度呼び出されます。

これにより再帰呼び出しが作成され、プログラムは何らかの条件が満たされるまでこの関数で反復を続けます。 通常、if...else 構造は再帰関数で使用され、1つのパスが再帰呼び出しを行い、もう 1つのパスが関数を終了します。 そうしないと、無限再帰が発生します。

再帰は、関数内から関数を繰り返し呼び出します。 再帰条件は、基本ケースが満たされるまで関数を再度呼び出します。

基本ケースは関数内に含まれており、基本ケースの条件が満たされるたびに実行を終了します。

コード：

void recursiveFun(int x) {
  if (x == 0) return;
  x = x - 1;
  recursiveFun(x);
}

上記の関数は、引数 x で一度呼び出されると、x はゼロになります。 値ゼロの x に遭遇すると、プログラムは新しい再帰呼び出しの生成を停止し、値 (ある場合) を下から上に返し始めます。

再帰はほとんどすべての問題を解決するために使用できますが、再帰が本当に役立つ場合もあります。 難しい問題や階層パターンに従う問題を処理するために一般的に使用されます。 より小さな副問題を解決することで、主な問題に対処します。

再帰の種類

直接再帰と間接再帰は、2 種類の再帰です。

直接再帰

再帰関数は、直接再帰によって自身の本体で直接呼び出します。

void recursion() { ....recursion(); }

コードでは、関数がそれ自身の本体または括弧内で自分自身を呼び出していることがわかります。

間接再帰

間接再帰では、関数は他の関数の本体で間接的に呼び出されます。

void func1() { ... func2(); }
void func2() { ... func1(); }

フィボナッチ数列

フィボナッチ数列は、連続する各数値が前の 2つの数値の合計である整数のセットです。 最初の 2つの数値 0 と 1、および 3 番目の数値は、最初の 2つの数値を加算して計算されます。

フィボナッチ数列を計算する式は次のとおりです。

例えば 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

3 番目の要素 1 は 0+1 の合計であることがわかります。 同様に、4 番目の数値 2 は、前の数値の合計です (1+1=2)。

したがって、シリーズの次の要素は 21+34 = 55 であると予測できます。

C++ のフィボナッチ数列

フィボナッチ数列を実装するために、入力を数値として取り、その量のフィボナッチ数列を出力できる再帰関数を実装できます。 たとえば、ユーザーが 8 を入力すると、シリーズの 8つの数字が出力されます。

コード：

#include <iostream>
using namespace std;

int fibonacci(int num) {
  if (num <= 1) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
  int num;
  cout << "Enter a number: ";
  cin >> num;
  for (int a = 0; a < num; a++) {
    cout << fibonacci(a) << " ";
  }
  return 0;
}

メイン関数では、ユーザーに数字を入力するように求めています。 その後、0 からその入力番号 num までループを反復し、反復子変数 a を Fibonacci 関数に渡しました。

このループは、ユーザーが入力した数値を num 回繰り返します。 関数 Fibonacci には、数値が 1 未満かどうかをチェックする if 条件があり、その数値を返します。

さもないと、それはfibonacci関数をnum-1およびnum-2に対して呼び出します。なぜなら、この系列の次の数は、前の2つの数、つまりn-1とn-2を合計して計算されるからです。

出力：

ユーザーが数値 9 を入力したため、フィボナッチ数列は 9つの値を含むように出力されました。