再帰さいきの基本きほん

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、再帰さいきを「関数かんすうが自分じぶんを呼よぶ書かき方かた」でなく、「問題もんだいを同おなじ形かたちの小ちいさい問題もんだいへ縮ちぢめる考かんがえ方かた」として見みることです。

再帰さいきで誤あやまりやすいのは、停止条件ていしじょうけんを忘わすれたり、何なにが小ちいさくなっているかが曖昧あいまいなまま呼よび出だすことです。この講義こうぎでは、停止条件ていしじょうけんと再帰呼さいきよび出だしの役割やくわりを分わけて見みます。

用語ようごと定義ていぎ

再帰さいきRecursion とは、ある問題もんだいを、それより小ちいさい同種どうしゅの問題もんだいに分わけて解とく方法ほうほうです。

停止条件ていしじょうけんBase case とは、それ以上いじょう分わけずにすぐ答こたえられる場合ばあいです。

方針ほうしん

まず「どこまで小ちいさくなれば直接ちょくせつ答こたえられるか」を決きめます。そのあと、「大おおきい問題もんだいをどう1 段階いちだんかい小ちいさくするか」を決きめます。

直感的ちょっかんてきな説明せつめい

階段かいだんを 1 段だんずつ下おりるように、問題もんだいを少すこしずつ小ちいさくしていき、一番下いちばんしたまで着ついたら答こたえを戻もどしていくのが再帰さいきです。

厳密げんみつな説明せつめい

見分みわけ方かた

• 同おなじ形かたちの小問題しょうもんだいへ分わけられるなら、再帰さいきを疑うたがいます。
• 停止条件ていしじょうけんが 1 行ぎょうで書かけないなら、まだ設計せっけいが曖昧あいまいな可能性かのうせいがあります。

最終形さいしゅうけい

一言ひとことでいうと

• 再帰さいきでは、関数かんすうの書かき方かたより「何なにが小ちいさくなっているか」を見みることが大切たいせつです。