再帰関数でフィボナッチ数列を書いてみる

再帰とは

関数の処理の中で同じ関数を呼び出すことで繰り返しを実現すること。
言い換えると、メソッドの中でそのメソッドを再び呼ぶこと。そうすることで、for文やwhile文のように処理が繰り返し実行されます。
では、フィボナッチ数列を使って具体的に見ていきます。

フィボナッチ数列とは

フィボナッチ数列とは、以下の式を満たす数列です。
0, 1, 2, 3, 5, 8, 13, 21, 34, 55...となっていきますね。
$$
F(n) =
\begin{cases}
n & \text{( n = 0, 1 )} \\
F(n-1) + F(n-2) & \text{( n > 2 )}
\end{cases}
$$

実装

実装例と実行結果はこのようになります。

実装例

class Fibo {
  public static void main(String[] args) {
      // メソッド呼び出し
      System.out.println(fibo(5)); 
  }

  static int fibo(int n) {
      if(n < 2) {
          return n;
      } 

      return fibo(n - 1) + fibo(n - 2);
  }
}

実行結果

5

解説

fiboメソッドでreturn fibo(n-1) + fibo(n-2)をしているので、以下のようなフロー図で処理を追っていきます。
矢印に書いてある数字は処理順番を示しています。
実線が呼び出す時、波線が戻り値を返す時を示しています。

まず、mainメソッドからfibo(5)を実行します。
ここからがfiboメソッドでの再帰処理の動き方です。

1. fibo(5)内でreturn fibo(n-1) + fibo(n-2)の、fibo(n-1)部分となるfibo(4)を実行
2. fibo(4)内でreturn fibo(n-1) + fibo(n-2)の、fibo(n-1)部分となるfibo(3)を実行
3. fibo(3)内でreturn fibo(n-1) + fibo(n-2)の、fibo(n-1)部分となるfibo(2)を実行
4. fibo(2)内でreturn fibo(n-1) + fibo(n-2)の、fibo(n-1)部分となるfibo(1)を実行
5. fibo(1)内でn = 1なので、return 1する
6. fibo(2)内でreturn fibo(n-1) + fibo(n-2)の、fibo(n-2)部分となるfibo(0)を実行
7. fibo(0)内でn = 0なので、return 0する
8. fibo(2)内で全てのメソッドが終了したのでreturn fibo(n-1) + fibo(n-2)として、return 1 + 0をする

同様に処理を進めていくと、最終的にfibo(5)の戻り値としてreturn 5されます。

まとめ

今回はフィボナッチ数列を例に再帰処理を見ていきました。
イメージしにくく詰まりやすい部分だと思います。
フィボナッチ数列の他にも、階乗や漸化式などでも再帰を使って実装ができます。
手を動かしデバッグをしながら理解を深めてみてください。
また、再帰処理を書く際のポイントも調べると出てくるのでそちらも見てみるといいと思います。

最後まで読んでいただきありがとうございました。