32.11 再帰関数の定義

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

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

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

let fibonacci(n) =
  if n = 0 then 0 else if n = 1 then 1 else ...

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

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

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

再帰関数の定義と利用

OCamlで再帰関数を定義する時には，

let rec 関数名(引数名1, 引数名2, ...) = 式

のように書きます．また，一度定義すると普通の関数と同じ方法で呼び出すことができます．
このように“let”の後に“rec”を付けることで，定義の式中に自分自身を呼び出せるようになります．なお，“rec”を書かないと自分自身は参照できず，関数が見つからないエラーになるか，以前に定義された同名の関数を呼び出して意図した通りの結果にならないことがあるので注意してください．

let fibonacci(n) = if n = 0 then 0 else if n = 1 then 1 else fibonacci(n - 1) + fibonacci(n - 2);;

Error: Unbound value fibonacci (* recを付けないとエラーになる *)

let fibonacci(n) = 0;;

val fibonacci : 'a -> int = <fun> (* もし以前に同じ名前の関数を定義していたら... *)

let fibonacci(n) = if n = 0 then 0 else if n = 1 then 1 else fibonacci(n - 1) + fibonacci(n - 2);;

val fibonacci : int -> int = <fun> (* 関数の定義はできるが... *)

fibonacci(8);;

- : int = 0 (* 期待通りの動作にならない *)

let rec fibonacci(n) = if n = 0 then 0 else if n = 1 then 1 else fibonacci(n - 1) + fibonacci(n - 2);;

val fibonacci : int -> int = <fun>

fibonacci(3);;

- : int = 2

fibonacci(8);;

- : int = 21

再帰関数のメカニズム

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

1. “fibonacci(3)”は関数が呼び出されて，
2. “if 3 = 0 then 0 else if 3 = 1 then 1 else 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 then 0 else if 2 = 1 then 1 else 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 then 0 else if 1 = 1 then 1 else fibonacci(1 – 1) + fibonacci(1 – 2)”になり，2つめの分岐の条件が“true”なので，
11. “1”になる．
12. “fibonacci(2 – 2)”（7.の右辺）は，
13. “fibonacci(0)”で，
14. “if 0 = 0 then 0 else if 0 = 1 then 1 else 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”をトレースすると次のようになります．

#trace fibonacci;;

fibonacci is now traced.

fibonacci(3);;

fibonacci <-- 3 fibonacci <-- 1 fibonacci --> 1 fibonacci <-- 2 fibonacci <-- 0 fibonacci --> 0 fibonacci <-- 1 fibonacci --> 1 fibonacci --> 1 fibonacci --> 2 - : int = 2

再帰関数の注意

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

let rec f(x) = f(x);;

val f : 'a -> 'b = <fun>

f(0);;

(* プログラムが止まらない *)

c

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

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

fibonacci(-1);;

Stack overflow during evaluation (looping recursion?). (* 計算が多すぎて限界を超えたというエラー *)

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

ことが重要と言えます．