わかりやすく 再帰 とは

自分を呼ぶ関数

第9回で、関数は仕事をまとめて名前をつけたもので、関数の中からほかの関数を呼ぶこともできました。
再帰は、そこからもう一歩進みます。関数が自分自身をもう一度呼ぶのです。
鏡の中の鏡のように、同じものがもう一重できます。

「もう一枚」を押すたびに、内側に同じ枠が一重ずつ増えます。

不思議ですが、少しこわくもあります。
こうして自分を呼び続けたら、永遠に止まらないのではないでしょうか。
そのとおりです。だから再帰には、どうしても必要なものが一つあります。

止まる場所が必要

二枚の鏡は本当にどこまでも続きますが、コンピュータは「永遠に」はできません。
そこで「かけらが十分に小さくなったら、そこで止まれ」という規則を一つ決めます。
この止まる規則がないと、いつまでも回り続けて崩れてしまいます。

止まるルールをオンにすると、3、2、1でぴたりと止まります。オフにすると、どこまでも下りていって崩れます。

この止まる場所を「床」と考えるとわかりやすいでしょう。
床に着くまでは自分を呼び続け、床に着いたらもう呼びません。
そうなると、問題をどう分けるかが要になります。

同じ問題の小さな版

再帰の本当の秘訣は、大きな問題を「一歩 + 同じだけど小さな問題」と見ることです。
階段全体は一段と残りの階段を足したもので、残りの階段も、一段小さいだけの同じ問題です。
どんどん小さくなって0段に着いたら、おしまいです。

「一段はがす」を押すたびに、階段が一段ずつ減ります。残った階段は、いつも「同じだけど小さな」問題です。

難しかった問題が、急にやさしくなります。
全部を一度に解く必要はなく、「一段」だけを片づけて、残りは同じ関数にまた任せればよいのです。
では、任せた仕事はどうやって戻ってくるのでしょうか。

行って、また戻ってくる

再帰は二つの方向に動きます。
まず、自分を呼んではまた呼び、床までずっと下りていきます。
床に着くと、今度は逆に上りながら、それぞれが自分の分を足していきます。
お皿を積み上げてから、上から順に片づけるのとまったく同じです。

「次のステップ」を押すと、1+2+3を床まで下りてから、上りながら6にまとめます。

この「下りて、上る」が再帰の心臓です。
下りるときは問題を分け、上るときは答えをまとめます。
積み重なった仕事が、床から順にほどけていくのです。

繰り返しの兄弟、そしてその先

再帰と繰り返し(第7回)は兄弟です。
どちらも同じことを何度もしますが、繰り返しは横にずらりと並べ、再帰は内側へ一重ずつ掘り下げていきます。
フォルダの中のフォルダのように、枝からまた枝が出るような仕事には、再帰がぴったりです。

押すたびに枝がまた分かれます。同じ規則が、ひとりでに木を描きます。

仕事をまとめて名前をつけた関数が(第9回)、ついに自分自身まで呼べるようになりました。
小さく分け、床で止まり、またまとめる。この一つの考え方が、フォルダ、返信への返信、迷路探しまで解いてしまいます。
次のレッスンでは、値を組にして入れる方法へ進みます。