再帰のきほん

自分自身を呼ぶ関数

前回、wa が nijou を呼ぶ形を追いました。呼ばれる相手が別の関数である必要はありません。自分自身を呼んでもかまいません。これが再帰です。

1 から n までの合計を求める関数です。最後の行で、自分と同じ名前の goukei を呼んでいます。初めて見ると、終わらない気がして落ち着かないはずです。なぜ終わるのかをはっきりさせるのが、このレッスンの目的です。

止まる理由は 2 つの部品にある

再帰する関数は、必ず 2 つの部品でできています。

1 つは、それ以上呼ばずに答えを返してしまう場所です。上の例では if (n = 1) の中の return 1 がそれにあたります。これを基底部と呼びます。この関数は、n が 1 のときの答えだけは自分で知っている、というわけです。

もう 1 つは、自分を呼ぶ場所です。上の例では最後の行で、これを再帰部と呼びます。ここで大事なのは、渡している引数が n ではなく n − 1 だということです。呼ぶたびに引数が 1 ずつ小さくなり、いつか必ず 1 になります。1 になれば基底部に入り、そこで呼び出しは止まります。

つまり再帰が終わる条件は、基底部があることと、呼ぶたびに引数が基底部へ近づくことの 2 つです。どちらか一方でも欠けると止まりません。たとえば再帰部を goukei(n) と書いてしまうと、引数がいつまでも小さくならず、基底部にたどり着けません。本試験でも、この 2 つのどちらが欠けているかを問う形が出ます。

展開して確かめる

止まることを納得する一番早い方法は、書き下してみることです。goukei(4) を展開します。

下まで降りきったところで 1 という具体的な数字が出ました。あとは、これを下から上へ順に代入して戻ります。goukei(2) が 3、goukei(3) が 6、goukei(4) が 10 です。

降りるときには答えが 1 つも決まらず、いちばん下に着いて初めて 1 つ目の答えが出て、そこから折り返して上へ戻る、という形になります。この折り返しが再帰の要です。

積み上がりは消えていない

降りていくあいだ、4 + □、3 + □ という計算は、右側が決まらないので保留されています。保留された計算は消えたわけではなく、順番に積み上げて置かれています。この置き場が呼び出しスタックです。

積み上がる高さのことを深さと呼び、前回の変数表で使った深さの列がそのまま使えます。降りるときに深さが増え、折り返してからは深さが減ります。

引数が基底部へ近づかないコードを書くと、この積み上がりが際限なく増えていきます。実際の計算機ではやがて置き場が足りなくなり、異常終了します。無限ループが時間を食いつぶすのに対し、無限の再帰は置き場を食いつぶす、と押さえておくと違いを説明できます。

次のレッスンでは、この降りて折り返す動きを、深さと戻り値の列を持った表で 1 段ずつ追います。