自分を 呼ぶ ときかた、再帰

自分を また 呼びます

ときかたが 自分を 呼ぶなんて
少し へんに きこえますね。
でも かんたんです。
「とく(5)」を とくには
「とく(4)」を とけば よく、
「とく(4)」を とくには
「とく(3)」を とけば いいのです。
同じ ときかたを
もっと 小さな 入力で また 呼ぶのです。

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

はこの 中に 同じ はこ、
その 中に また 同じ はこ。
かがみの 中の かがみの ように。
かわるのは ただ 一つ、
入力が 一つずつ 小さく なります。
小さく 小さく なって いくと
いつか とても 小さな、
すぐ とける もんだいに なります。

止まる ゆか

自分を 呼びつづけるだけなら
どう なるでしょう?
かぎりなく 下ります。
だから 再帰には
「ここで 止まれ」と いう
ゆかが かならず ひつようです。
「入力が 1に なったら
もう 呼ばず すぐ こたえる」、
そんな やくそくです。

ゆか あり vs なし。(あり: 1で 止まる · なし: かぎりなく 下る)

ゆかが あれば
下りて そこで ぴたりと 止まり、
そこから こたえを もって 上ります。
ゆかが なければ
0、マイナスへ かぎりなく 下りて
いつまでも こたえが でません。
だから 再帰を つかう ときは
まず ゆかを きめます。

つもって 解けます

再帰が こたえを つくる ようすは
二歩です。
下りる ときは
こたえを ひとまず あとまわしに して
自分を 呼びつづけ、つみます。
ゆかに つくと
こんどは ぎゃくに 上りながら
つんだ ものを 一つずつ
合わせて こたえを かんせい します。

下りながら つみ、ゆかから ぎゃくに 合わせます。(かけ(4) = 4x3x2x1 = 24)

下りる ときは こたえが 見えなくて
少し もどかしいかも しれません。
でも ゆかを ふんだ しゅんかん
ぎゃくに すらすら 解けます。
つんだ ものが おおいほど
上る とき 合わせる ものも おおい。
だから あまり 深く つむと
たいへんに なりますが、
その はなしは つぎに。

分割統治と 一つの もの

前回を 思い出して みましょう。
大きな もんだいを 半分に わって
それぞれ といて 合わせましたね。
その「わって それぞれ とく」が
じつは 再帰です。
とく(8)が
とく(4)と とく(4)を 呼び、
その 4たちが また
とく(2)を 呼ぶのです。

わる ことを 再帰 呼び出しで。(とく(8) → とく(4)·とく(4) → とく(2)×4)

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

再帰を 一行で

再帰は 三つの はしらです。
自分を もっと 小さな 入力で 呼び、
止まる ゆかが あり、
つもって ぎゃくに 解けます。
この 三つさえ そろえば
ふくざつに 見える もんだいも
「自分より 小さな 自分」に
そっと まかせて とけます。

三つの はしらを 順に。(自分を 呼ぶ → 止まる ゆか → つもって 解ける)

ただ 一つ 気を つける ことが あります。
わって いくと 同じ 小さな もんだいを
なんども くりかえし とく ときが あります。
同じ こたえを なんども もとめると
時間が もったいない。
一ど といた こたえを 書いておいて
また つかう ちえが あるのですが、
それが まさに つぎの はなしです。