自分を呼ぶ関数、再帰

自分を呼ぶ関数

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

押してみて。押すたびに、中に同じわくが一枚ずつふえます。

ふしぎですが、少しこわくもあります。
こうやって自分を呼び続けたら、
永遠にとまらないのでは?
そのとおり。だから再帰には、ぜったい必要なものが一つあります。

とまる所が必要です

鏡二つは本当にきりなく入っていきますが、
コンピューターは「永遠に」ができません。
だから、ルールを一つ決めます。
「かけらが十分に小さくなったら、そこでとまれ。」
このとまるルールがないと、永遠に回ってくずれます。

とまるルールをつけると3、2、1でぴたっと止まります。消すと、きりなく下がってくずれます。

このとまる場所を「ゆか」と思うとかんたんです。
ゆかにつくまでは自分を呼び続け、
ゆかにつくと、もう呼びません。
では、どう分けるかが大事になります。

同じ問題の小さい版

再帰の本当のコツはこれです。
大きな問題を「一歩 + 同じだけど小さい問題」と見るのです。
階段ぜんたい = 一だん + のこりの階段。
「のこりの階段」も同じ問題、一だん小さいだけ。
小さく小さくなって、0だんにつけば終わりです。

一だんずつはがしてみて。のこりは毎回「同じだけど小さい」問題です。

むずかしかった問題が、急にかんたんになります。
ぜんぶを一度にとく必要はありません。
「一だん」だけ片づけて、のこりは同じ関数にまたまかせればいいのです。
では、まかせた仕事は、どうもどってくるのでしょう?

行って、またもどる

再帰は二つの方向に動きます。
まずゆかまでずっと下ります(自分を呼んで、また呼んで)。
ゆかについたら、今度は逆にもどりながら、
それぞれが自分のぶんをたします。
お皿をつみ上げて、上からまたかたづけるのと同じです。

一歩ずつ押してみて。1+2+3をゆかまで下りて、もどりながら6に集めます。

この「下りてのぼる」が再帰の心臓です。
下りるときは問題を分け、
のぼるときは答えを合わせます。
つみ上がった仕事が、ゆかから順にほどけていきます。

くりかえしの兄弟、その先へ

再帰とくりかえし(7話)は兄弟です。
どちらも「同じことを何回も」しますが、
くりかえしは横にずらりとならべ、
再帰は中へ一枚ずつもぐっていきます。
フォルダの中のフォルダのように、枝からまた枝が出ることには、再帰がぴったりです。

一回押すと、枝がまた分かれます。同じルールが、ひとりでに木をえがきます。

まとめて名前をつけた関数が(9話)、
いまや自分自身まで呼べるようになりました。
小さく分け、ゆかでとまり、また集める。
この一つの考えが、フォルダ、コメントへのコメント、めいろ解きまでときます。
次は、いくつもの値を組にしてしまう方法へ進みます。