第六の巻 再帰

中段 / 目安 25分

カメ師範が六本目の巻物を解きました。中には、木の枝のような図が一枚だけ描かれています。

「自分を呼ぶ関数を書け。階乗、そしてフィボナッチ。呼び出しの連なりを紙に描いてから書くのじゃ」

師範は湯呑みを置いて続けます。「ループは、上から下へ一本道じゃ。再帰は違う。自分より小さい問題を、もう一人の自分に任せる。任せた先が答えを持って帰ってくるのを信じて待つ。信じられぬ者は、この技を使えぬ」

この巻の掟は一つです。ループを書いてはなりません。for も while も使わず、関数が自分自身を呼ぶ形だけで組み立ててください。

再帰で最初に決めるのは、進む道ではなく止まる場所です。止まる条件を書き忘れた再帰は、自分を無限に呼び続けて力尽きます。階乗なら「0の階乗は1」、フィボナッチなら「0番目は0、1番目は1」。ここが地面です。地面を先に置いてから、その上に「自分より小さい自分に任せる」一行を乗せます。

完成条件

factorialAndFib という関数を1つ定義してください。どの言語で解いても関数名は factorialAndFib にしてください。Python でも snake_case ではなく、この綴りのまま使います。

引数は2つです。n は階乗を求める数、m はフィボナッチの番号です。返すのは次の形をした1つの文字列です。

数の前後の空白と、区切りの / の形を、この見本のとおりに揃えてください。

階乗とフィボナッチの決まりは次のとおりです。

• 階乗は、0 の階乗が 1、それ以外は n かける (n-1) の階乗
• フィボナッチは、0番目が 0、1番目が 1、それ以外は直前2つの和

階乗とフィボナッチはそれぞれ別の補助関数に切り出し、factorialAndFib はその2つを呼んで文字列を組み立てるだけにしてください。1つの関数に詰め込むと、どちらの再帰が壊れているのか分からなくなります。

フィボナッチの素朴な再帰は、番号が大きくなると呼び出しが爆発的に増えます。この巻では m は 25 までしか渡しません。

進め方

白紙から書いてください。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。1つも開けずに通せたら、その問題は自分のものです。

開かずに10分粘って進まないなら、①だけ開けてください。粘る時間そのものには価値がありません。価値があるのは、自分で書いた行が動いた瞬間です。

書く前に、紙に fib(5) の呼び出しを枝分かれで描いてみてください。fib(5) が fib(4) と fib(3) を呼び、その fib(4) がまた fib(3) と fib(2) を呼ぶ。同じ枝が何度も現れることに気づけば、この技の速さと遅さの両方が一度に見えます。

1. 関数名は4言語すべてで factorialAndFib にすること(Python も snake_case にしない)
2. 引数は n(階乗を求める数)と m(フィボナッチの番号)の2つ
3. for も while も使わず、関数が自分自身を呼ぶ再帰だけで組み立てること
4. 階乗は0の階乗が1、それ以外は n かける (n-1) の階乗
5. フィボナッチは0番目が0、1番目が1、それ以外は直前2つの和
6. 階乗とフィボナッチはそれぞれ別の補助関数に切り出すこと
7. 戻り値は「5! = 120 / fib(10) = 55」の形をした1つの文字列であること
8. 数の前後の空白と区切りの半角スラッシュの位置を見本どおりに揃えること