再帰のトレース

深さと戻り値の 2 列で追う

前回、再帰は降りきってから折り返して戻る形だと確かめました。今回はそれを表で追います。科目 B でいちばん配点をこぼしやすい場所なので、追いかたの型をここで作ってしまいます。

再帰のトレースがふつうの表と違うのは、同じ変数名が同時にいくつも存在する点です。kaijou(3) の中から kaijou(2) を呼んだとき、n という変数は 2 つあります。1 段目の n は 3 のまま、2 段目の n が 2 です。これを 1 つの欄に書こうとすると必ず壊れます。

そこで、深さの列と戻り値の列を使います。深さの列は、いま何段目にいるかを表します。n の欄には、いまいる段の n だけを書きます。1 段目の 3 は消えたわけではなく、上に置いたまま待っている、と読みます。

戻り値の列には、直前の return が返した値を書きます。降りているあいだは、まだ何も返っていないので全角ダッシュのままです。この列に初めて数字が入る行が、折り返し地点です。

折り返しの前と後で表の読み方が変わる

降りているあいだ、深さは 1 段ずつ増え、n は 1 ずつ小さくなります。このあいだ 5 行目の掛け算はどれも保留です。3 × □、2 × □ という形で置かれているだけで、答えは 1 つも出ていません。

基底部に着いて 1 が返った瞬間から、向きが変わります。深さは 1 段ずつ減り、保留していた掛け算が下から順に片づいていきます。表の上では、同じ 5 行目が深さを変えながら何度も出てきます。行番号が同じでも別の段の話なので、深さの列を見て区別してください。

戻る先は必ず呼び出しの行

再帰で迷ったら、戻る先を確かめます。return したあとに進む先は、自分を呼んだ行です。この関数では 5 行目です。つまり、基底部の return 1 のあとは 5 行目に戻り、そこで n × 1 を計算してまた 5 行目の return が動き、また 5 行目に戻ります。

同じ行を行ったり来たりしているように見えますが、深さが 1 段ずつ違います。ここを深さの列で押さえられれば、再帰は迷路ではなくなります。

追う前の下ごしらえ

表に入る前に、展開だけ書いておくと安全です。

答えは 6 だと先にわかります。答えがわかった状態で表を埋めるのは、ずるではありません。本試験でも、まず何段で止まるかを見てから表を作るほうが速くて確実です。

この下ごしらえには、もう 1 つ効き目があります。基底部に着く前に引数が行き過ぎないかを、表を書く前に確かめられることです。今回は 3 から 1 ずつ減るので、ちょうど 1 で止まります。もし 2 ずつ減る書き方なら、1 を飛び越えてしまうかもしれません。展開の 3 行を書く手間で、この種の取り違えを先に潰せます。

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

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