再帰 アルゴリズム わかりやすく

自分をまた呼ぶ

解き方が自分自身を呼ぶと聞くと、少し不思議に思えます。でも、じつは単純です。
「解く(5)」を解くには「解く(4)」を解けばよく、「解く(4)」を解くには「解く(3)」を解けばよいのです。
同じ解き方を、もっと小さな入力でもう一度呼んでいるだけです。

同じ箱が、もっと小さな入力で自分をまた呼びます。（解く(5) → 解く(4) → … → 解く(1)）

箱の中に同じ箱、その中にまた同じ箱。鏡の中の鏡のようです。
変わるのはただ一つ、入力が一つずつ小さくなることです。
小さく、また小さくなっていけば、いつかすぐ解ける、とても小さな問題になります。

止まる底

自分を呼び続けるだけだと、どうなるでしょうか。果てしなく下りていきます。
だから再帰には、「ここで止まれ」という底が必ず要ります。
「入力が1になったら、もう呼ばずにすぐ答える」といった約束です。

底があるとき vs ないときを比べます。あれば1で止まり、なければ果てしなく下りていきます。

底があれば、下りていく途中でぴたりと止まり、そこから答えを持って上がってきます。
底がなければ、0、マイナスへと果てしなく下りて、いつまでも答えが出ません。
だから再帰を使うときは、まず底を決めなければなりません。

積もってから解ける

再帰が答えを作る様子は、二つの歩みに分かれます。
下りるときは答えをいったん後回しにして、自分を呼び続けながら積み上げます。
底に着いたら、今度は逆に上がりながら、積んでおいたものを一つずつ合わせて答えを完成させます。

下りながら積み、底から逆に合わせます。（積(4) = 4x3x2x1 = 24）

下りているあいだは答えが見えないので、少しもどかしいかもしれません。
でも底に触れたとたん、逆向きにすらすら解けていきます。積もったものが多いほど、上がるときに合わせるものも多くなります。
あまり深く積もるとコンピュータも手に余る、ということは覚えておくとよいでしょう。

分割統治と一体

前のレッスンを思い出してください。大きな問題を半分に割って、それぞれ解いて合わせました。
その「割ってそれぞれ解く」が、じつは再帰です。
解く(8)は解く(4)と解く(4)を呼び、それぞれの解く(4)はまた解く(2)を二回ずつ呼びます。

割ることを再帰呼び出しにします。（解く(8) → 解く(4)·解く(4) → 解く(2)×4）

だから分割統治と再帰は別々ではなく、一体です。割ること = 自分をまた呼ぶこと。
かけらがもう割れないほど小さくなれば、それが底で、小さな答えが上へ合わさっていくのが、積もってから解ける流れです。
これまで見てきたことが、すべてここに集まります。

再帰を一行で

再帰は三本の柱で立っています。自分をもっと小さな入力で呼び、止まる底があり、積もってから逆に解ける。
この三つさえそろえば、複雑に見える問題も「自分より小さな自分」にそっと任せて解けます。

三本の柱を順に押して、まとめます。（自分を呼ぶ → 止まる底 → 積もって解ける）

ただし、気をつけることが一つあります。割っていくと、同じ小さな問題を何度もくり返し解くことがあります。
同じ答えを何度も求め直すのは時間のむだです。
一度解いた答えを書きとめておき、また使う工夫があります。それが次の話です。