31.11 再帰関数の定義

ここでは，フィボナッチ数の計算をしてみましょう．
フィボナッチ数とは，ある数列の値のことで，1 つの項はその 1 つ前と 2 つ前の項の和になっているようなものを言います．通常は最初 2 つの項を 0, 1 とするので，

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

と値が進んでいきます．数学の言葉で書くと，“an+2=an+1+an (n=0, 1, …), a0=0, a1=1” を満たす数列 “an” の値を求めることになります．
以下では，最初 2 つの項を便宜上 “0 番目”，“1 番目” と呼んで，0 以上の整数 “n” に対して n 番目のフィボナッチ数を求めることを考えます．
フィボナッチ数を計算するメソッド “fibonacci” を作るとして，どのように書けばよいでしょうか？とりあえず最初 2 つの値は決まっているので，条件分岐を使って，

public static int fibonacci(int n) {
  if(n == 0) {
    return 0;
  } else if(n == 1) {
    return 1;
  } else {
    return ...;
  }
}

と書き出せばよいのはわかります．
では，“…” の部分には何と書くのでしょうか？(n-1) 番目と (n-2) 番目のフィボナッチ数の和なので，

fibonacci(n - 1) + fibonacci(n - 2)

がふさわしいです．つまり，“fibonacci” というメソッドを定義するために自分自身を呼び出すことになります．
一般に，このように定義の処理の中で自分自身を呼び出すことがある関数を再帰関数と言います．

再帰関数の定義と利用

Java では再帰関数（メソッド）を定義するのに特別なことを書く必要はありません．メソッドを定義してその中の処理で自分自身を呼び出せば再帰メソッドです．
なので，“fibonacci” は次のようになります．

// Program.java: フィボナッチ数 class Program { public static int fibonacci(int n) { if(n == 0) { return 0; } else if(n == 1) { return 1; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } public static void main(String[] args) { System.out.println(fibonacci(3)); System.out.println(fibonacci(8)); } }

2 21

最初に書いた数列と照らし合わせて，正しく計算できていることがわかります．

再帰関数のメカニズム

以上によって再帰関数が使えるようになったのですが，どのような仕組みで再帰関数は実現されているのでしょうか？定義の中に定義したいものを書くのは，定義になっていないようにも思えます．
しかし，このことはhwb31.10 プログラム実行の処理をよく理解することで謎でも何でもないことがわかります．
つまりプログラム言語の関数というのは，「引数がそろって初めて処理が行われて計算結果が求まる」というのが重要です．なので，関数を定義する時は定義式がきちんと戻り値を持つことを確認する必要がなく，引数を指定して呼び出された時にさらに自分自身を何度か呼び出したりして最終的に値を返せばよいということになります．そもそも数学で漸化式による数列の定義がこの理屈と似たようなものになっています（適切な初期条件の下では，数学的帰納法によりすべての項が定義できることがわかるので数列全体が定義できたことになる）．
これをふまえて，“fibonacci(3)” の値がどのように計算されるか書き出してみましょう

  1. “fibonacci(3)” は関数が呼び出されて，
  2. “if(3 == 0) { return 0; } else if(3 == 1) { return 1; } else { return fibonacci(3 – 1) + fibonacci(3 – 2); }” になり，条件分岐は両方 “false” なので，
  3. “fibonacci(3 – 1) + fibonacci(3 – 2)” になる．
  4. “fibonacci(3 – 1)”（3. の左辺）は，
  5. “fibonacci(2)” で，
  6. “if(2 == 0) { return 0; } else if(2 == 1) { return 1; } else { return fibonacci(2 – 1) + fibonacci(2 – 2); }” になり，また条件分岐は両方 “false” なので，
  7. “fibonacci(2 – 1) + fibonacci(2 – 2)” になる．
  8. “fibonacci(2 – 1)”（7. の左辺）は，
  9. “fibonacci(1)” で，
  10. “if(1 == 0) { return 0; } else if(1 == 1) { return 1; } else { return fibonacci(1 – 1) + fibonacci(1 – 2); }” になり，2つめの分岐の条件が “true” なので，
  11. “1” になる．
  12. “fibonacci(2 – 2)”（7. の右辺）は，
  13. “fibonacci(0)” で，
  14. “if(0 == 0) { return 0; } else if(0 == 1) { return 1; } else { return fibonacci(0 – 1) + fibonacci(0 – 2); }” になり，最初の分岐により，
  15. “0” になる．
  16. “1 + 0” が 7. になり，
  17. “1” で，これが “fibonacci(2)” ひいては 3. の左辺である．
  18. “fibonacci(3 – 2)”（3. の右辺）は，
  19. “fibonacci(1)” で，9. と同様にして，
  20. “1” になる．
  21. “1 + 1” が 3. になり，
  22. “2” で，これが “fibonacci(3)” の値．

また，“fibonacci” の呼び出しを確認すると次のようになります．

// Program.java: フィボナッチ数　デバッグ class Program { public static int fibonacci(int n) { System.out.println("fibonacci(" + n + ")"); int result; if(n == 0) { result = 0; } else if(n == 1) { result = 1; } else { result = fibonacci(n - 1) + fibonacci(n - 2); } System.out.println("fibonacci(" + n + ") = " + result); return result; } public static void main(String[] args) { System.out.println(fibonacci(3)); } }

fibonacci(3) fibonacci(2) fibonacci(1) fibonacci(1) = 1 fibonacci(0) fibonacci(0) = 0 fibonacci(2) = 1 fibonacci(1) fibonacci(1) = 1 fibonacci(3) = 2 2

再帰関数の注意

再帰関数を使えば，自然な発想で関数の定義を書くことができますが，いろいろと注意点があります．その最たるものが，自分自身を呼び出すことを繰り返して，プログラムが終わらなくなってしまうことです．
次の例を見てみましょう．

public static int f(int x) {
  return f(x);
}
public static void main(String[] args) {
  System.out.println(f(0));
}

Exception in thread "main" java.lang.StackOverflowError at Program.f(Program.java:4) at Program.f(Program.java:4) at Program.f(Program.java:4) at Program.f(Program.java:4) at Program.f(Program.java:4) // 計算が多すぎて限界を超えたというエラー　以下略

これを防ぐためには，

  • 再帰的に関数を呼び出す時は同じ引数を使わず，
  • 何らかの条件分岐を使って，再帰呼び出しが行われないような分岐を作る

ことが必要になります．
また，一見きちんとできていそうな今回のメソッド “fibonacci” ですが，それでも落とし穴があります．

System.out.println(fibonacci(-1));

Exception in thread "main" java.lang.StackOverflowError at Program.fibonacci(Program.java:4) at Program.fibonacci(Program.java:9) at Program.fibonacci(Program.java:9) at Program.fibonacci(Program.java:9) at Program.fibonacci(Program.java:9) // 以下略

このように“n”として負の数を指定すると，“n – 1” や “n – 2” も負の数なので，再帰呼び出しが止まる “0” や “1” にたどり着きません．
ですので，

  • 再帰関数を作る時は，すべての引数に対して何らかの計算結果が返されるようにする，
  • または再帰関数を呼び出す時は，計算が止まらなくなるような引数を指定しない

ことが重要と言えます．