再帰呼び出しの動きを追う

再帰関数は関数内で自分自身を呼び出し、そのたびに大きな問題が小さな問題になるように異なる引数を渡していく。ということだが感覚的に把握できてないので動きをできるだけ噛み砕いてみようと思う。

内容的には以下について言及する

  1. 階乗計算（factorial）
  2. フィボナッチ数の計算（fibonacci number）
  3. ユークリッドの互除法を使った最大公約数の計算（greatest common divisor）
  4. 末尾再帰（tail recursion）

階乗計算（factorial）

まずは次の階乗計算を行うコードを書いてみる

$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

実行結果

Factorial of 5 is 120

実行結果にあらわれるまでのプログラムは次のように動いている。

  1. まず最初に main 関数で factorial(5) を呼ぶ。
  2. factorial(5) の中で factorial(4) を呼ぶ。
  3. factorial(4) の中で factorial(3) を呼ぶ。
  4. factorial(3) の中で factorial(2) を呼ぶ。
  5. factorial(2) の中で factorial(1) を呼ぶ。
  6. factorial(1) の中で factorial(0) を呼ぶ。
  7. factorial(0) の中で終了条件に入る。ここから値が帰っていく。
  8. factorial(0) が factorial(1) に 1 を返す。
  9. factorial(1) が 1 * factorial(0) を計算して 1 を factorial(2) に返す。
  10. factorial(2) が 2 * factorial(1) を計算して 2 を factorial(3) に返す。
  11. factorial(3) が 3 * factorial(2) を計算して 6 を factorial(4) に返す。
  12. factorial(4) が 4 * factorial(3) を計算して 24 を factorial(5) に返す。
  13. factorial(5) が 5 * factorial(4) を計算して 120 を呼び出し元の main 関数に返す。

階乗の例では、再帰呼び出しは終了条件になるまで自分自身を繰り返し呼び続ける。終了条件で値を返すのをきっかけに値を呼び出し元へ返し続ける。

ちなみにリストの 1~6 までを winding といい 7 以降を unwinding という。

下の数式は一行目の $factorial(5)$ の内部で二行目の $5 \times factorial(4)$ を呼んでおり、$factorial(0)$ まで繰り返されていることをイメージしやすくなるように書いてみた。

$$ \begin{align} 5! &= factorial(5) \\ 5! &= 5 \times factorial(4) \\ 5! &= 5 \times 4 \times factorial(3) \\ 5! &= 5 \times 4 \times 3 \times factorial(2) \\ 5! &= 5 \times 4 \times 3 \times 2 \times factorial(1) \\ 5! &= 5 \times 4 \times 3 \times 2 \times 1 \times factorial(0) \\ \end{align} $$

$factorial(0)$ まで再帰呼び出しを行ってから、$factorial(5)$ まで値を返していくということが分かった。

ここでもう一度コードに戻って見てみると

前よりも動きが把握できている！（ような気がする）

上記の単純な再帰呼び出しコードで階乗計算を行うことができるのだが、再帰関数の作り方は次のふたつが必要っぽいことが分かった。

フィボナッチ数（fibonacci number）

次はフィボナッチ数を使って、階乗計算よりも少し複雑な例で動きを追ってみる

フィボナッチ数とは以下の式で定義される。

$$ \begin{eqnarray} f_{0} &=& 0 \\ f_{1} &=& 1 \\ f_{n+2} &=& f_{n}+f_{n+1} (n \geq 0) \end{eqnarray} $$

上記の式で計算される数列をフィボナッチ数列といい、以下のような数列になる。

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

では、フィボナッチ数を計算するコードを書いてみる

出力結果

Fibonacci(3)=2

実行結果にあらわれるまでのプログラムは次のように動いている。

  1. fibonacci(4) をmain関数から呼ぶ
  2. fibonacci(4) 内部の式を展開すると v := fibonacci(3) + fibonacci(2) となる。前方の fibonacci(3) を先に呼ぶ
  3. fibonacci(3) 内部の式を展開すると v := fibonacci(2) + fibonacci(1) となる。前方の fibonacci(2) を先に呼ぶ
  4. fibonacci(2) 内部の式を展開すると v := fibonacci(1) + fibonacci(0) となる。前方の fibonacci(1) を先に呼ぶ
  5. fibonacci(1) は 1 を返しリスト4に戻る
  6. リスト4の後方の fibonacci(0) を呼ぶ
  7. fibonacci(0) は 0 を返しリスト4に戻る
  8. リスト4では 1 + 0 を計算して 1 をリスト3に返す
  9. リスト3の後方の fibonacci(1)を呼ぶ
  10. fibonacci(1) は 1 を返しリスト3に返す
  11. リスト3では 1 + 1 を計算して 2 をリスト2に返す
  12. リスト2の後方の fibonacci(2) を呼ぶ
  13. fibonacci(2) 内部の式を展開すると v := fibonacci(1) + fibonacci(0) となる。前方の fibonacci(1) を先に呼ぶ
  14. fibonacci(1) は 1 を返しリスト13に戻る
  15. リスト13の後方の fibonacci(0) を呼ぶ
  16. fibonacci(0) は 0 を返しリスト13に戻る
  17. リスト13では 1+0 を計算して 1 をリスト2に返す
  18. リスト2ではリスト11の2とリスト13の1を合計して 3 をリスト1に返す

再帰関数の呼び出しと戻りの動きがイメージができるようになってきた気がする。

リスト4とリスト13で fibonacci(2) の計算を行っているので、このあと引数の値を 5,6... と上げていくと同じ計算を何度も行うことになり無駄な計算をすることになってしまうなぁと思ったので試しに手元のマシンで試したところ、引数を 40 にしたくらいからちょっともっさりしたレスポンスになり、45 では明らかにレスポンスが遅いと感じるようになってしまった。
ここでちょっと調べたところメモ化再帰という最適化技法があるとのことだったのでコードにしてみた

引数を 45 にしても 100 にしても全然速い。仕事でコード書くときに普通にやるような対応だなぁと思ったんですが、メモ化というのはプログラムの高速化のための最適化技法の一種であるとのことで、ちゃんとした名前のある方法だったとは思いもよらず勉強になりました。
私がどこかで「あぁ、メモ化しましょうか」って言葉を発したらここで学んだことを使ってるってわけです。

最大公約数（greatest common divisor）

次はユークリッドの互除法を使って最大公約数（GCD）を求める

12560 と 18232 の最大公約数を求める場合

  1. 最初に大きい方の値を小さい方の値で割ると余り 5672 が得られる
  2. 次に「割る値」を「余り」で割る。これを割り切れるまで繰り返す。
    1. 12560 割る 5672 の余りは 1216
    2. 5672 割る 1216 の余りは 808
    3. 1216 割る 808 の余りは 408
    4. 808 割る 408 の余りは 400
    5. 408 割る 400 の余りは 8
    6. 400 割る 8 の余りは 0
  3. 割り切れたときの「割る値」が最大公約数

これをコードにするとこうなる

出力結果

GCD(18232, 12560) = 8

プログラムの動きはコードの前に書いたリストのままなので割愛するが、コードの11行目で再帰関数の値を直接返しているので、終了条件で返した値 8 がそのまま main 関数の呼び出し元まで返っている。

末尾再帰（tail recursion）

末尾再帰（tail recursion）とは、再帰関数の中で実行する最後の処理ステップが再帰呼び出しになっている特別なケースの再帰のことである。
出典 : 『データ構造とプログラミング』鈴木一史 2018年3月

うまく説明できないので引用させてもらったんですが、とりあえずコードを見てみよう。

実行結果

factorialTail(5) = 120

コードの動きは再帰呼び出しごとに第1引数を n-1 して n == 0 になるまで繰り返す。第2引数は n*acc と累積していく。

実行結果に現れるまでの動きを追う

  1. main 関数で factorialTail(5, 1) を呼ぶ。第2引数は累積のデフォルト値なので 1
  2. factorialTail(5, 1) の内部の式を展開すると、第1引数に 5-1 の結果と第2引数に 5*1 の結果を割り当てて factorialTail(4, 5) を呼ぶ
  3. factorialTail(4, 5) の内部の式を展開すると、第1引数に 4-1 の結果と第2引数に 4*5 の結果を割り当てて factorialTail(3, 20) を呼ぶ
  4. factorialTail(3, 20) の内部の式を展開すると、第1引数に 3-1 の結果と第2引数に 3*20 の結果を割り当てて factorialTail(2, 60) を呼ぶ
  5. factorialTail(2, 60) の内部の式を展開すると、第1引数に 2-1 の結果と第2引数に 2*60 の結果を割り当てて factorialTail(1, 120) を呼ぶ
  6. factorialTail(1, 120) の内部の式を展開すると、第1引数に 1-1 の結果と第2引数に 1*120 の結果を割り当てて factorialTail(0, 120) を呼ぶ
  7. factorialTail(0, 120) では終了条件に入るので、第2引数の 120 をリスト6に返す
  8. リスト6から1の main 関数まで 120 をそのまま返す

要は再帰呼び出ししてる関数の返り値をそのままリターンしてるってことっぽい。
よく見たらユークリッドの互除法のコードも同じ構造なので上記の gcd() 関数も末尾再帰になるのか。

末尾再帰は

コードを繰り返しや反復（ for ループや while ループ)などに変換することが可能で、計算処理の高速化ができる。
出典 : 『データ構造とプログラミング』鈴木一史 2018年3月

とある。コードにするとこうかな。

実行結果

factorialLoop(5) = 120

感想のようなもの

再帰呼び出しの動きは、読んでも分からないが書いたら分かるようになった気がする。

おわり