再帰の頻出パターン

自分を 2 回呼ぶ再帰

前回の階乗は、1 か所で自分を 1 回だけ呼ぶ形でした。これを線形再帰と呼びます。降りて折り返すだけなので、道は一本道です。

本試験でもう 1 つよく出るのが、1 行の中で自分を 2 回呼ぶ形です。二分再帰と呼びます。

return fib(n - 1) + fib(n - 2)

一本道だったものが、ここで枝分かれします。追うのがむずかしくなるのは分岐そのものではなく、左の枝から持ち帰った値を、右の枝を追っているあいだ持ち続けなければならない点です。今回のトレースでは、この持ち続ける値を控えという列に置いて追います。

順番は左の枝を最後まで、それから右の枝

枝分かれといっても、2 つの呼び出しが同時に動くことはありません。左の fib(n − 1) を呼び、その中でさらに枝分かれが起きても、そちらを最後まで片づけて値を持ち帰ります。持ち帰ってから、はじめて右の fib(n − 2) を呼びます。

ですから道順は、いちばん左の枝を先端まで降り、そこから折り返し、右へ移り、また降りる、という形になります。木の絵で言えば、左端の葉から順に訪ねていくことになります。この順番は、あとの章で学ぶ木の走査とまったく同じ考え方です。

基底部が 2 つ必要になることがある

二分再帰では、基底部の書き方に注意が必要です。上の式は n − 1 と n − 2 の 2 通りに減るので、1 だけを基底部にすると、n が 2 のときに n − 2 が 0 になって基底部を飛び越えてしまいます。飛び越えると止まりません。

そこで今回のコードでは if (n ≦ 2) と書きます。1 と 2 のどちらで来ても受け止められるようにするわけです。誤ったコードを選ばせる問題では、この受け止めそこないがよく仕込まれます。減りかたが 2 通りあるなら、基底部もその 2 通りを全部受け止められるかを確かめてください。

同じ計算を何度もしている

今回追う fib(4) では、fib(2) が 2 回呼ばれます。左の枝の中で 1 回、右の枝で 1 回です。値は同じですが、計算し直しています。n が大きくなるほどこの重複は急激に増え、実行時間が跳ね上がります。

二分再帰は書きやすいけれど、素直に書くと同じ計算を繰り返してしまうことがある、という性質は覚えておく価値があります。あとの章の計算量の話につながります。

深さは意外に浅い

呼び出しの回数は多くても、同時に積み上がる段数は多くありません。左の枝を片づけて戻ってから右へ行くので、積み上がるのは木の高さぶんだけです。今回も、呼び出しは 6 回起きますが、深さは 3 までしか行きません。

回数と深さは別物です。表の深さの列が 3 を超えないことを、自分の目で確かめてください。

では下のコードを追ってください。行番号は 1 行目から数え、空行も 1 行として数えます。

課題

  1. 各行を実行したあとの値を入れる
  2. n の欄には、いまいる段の n だけを入れる
  3. 控えを使って足し算をしたら、控えは — に戻す
  4. 深さは呼び出しで 1 増やし、return で 1 減らす

ヒント

1 / 14 行目のトレース

1○整数型: fib(整数型: n)
2 if (n ≦ 2)
3   return 1
4 endif
5 return fib(n - 1) + fib(n - 2)
6 
7○整数型: main()
8 return fib(4)
実行した行深さn控え戻り値
実行前0———
8 行目

8 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。