第六の巻 再帰

中段 / 目安 25分

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

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

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

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

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

完成条件

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

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

5! = 120 / fib(10) = 55

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

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

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

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

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

進め方

ひな形の「課題」と書かれた部分から始めてください。初期化や補助処理は完成済みです。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。ヒントは必要に応じて使い、書いた処理を自分で追えることを目標にします。

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

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

戻り値で計算する再帰

別の題材として、階段を1段ずつ下りる回数を求めます。0段なら0回、それ以外は1回下りたあとに残りを任せます。steps(3) は 1 + steps(2)、さらに 1 + (1 + steps(1)) へ進み、steps(0) の 0 が戻ると順に 1、2、3 が返ります。関数を呼ぶ式は、その戻り値に置き換わって計算されます。

Python

def steps(level):
    if level == 0:
        return 0
    return 1 + steps(level - 1)

JavaScript

function steps(level) {
  if (level === 0) {
    return 0;
  }
  return 1 + steps(level - 1);
}

TypeScript

function steps(level: number): number {
  if (level === 0) {
    return 0;
  }
  return 1 + steps(level - 1);
}

Java

static int steps(int level) {
    if (level == 0) {
        return 0;
    }
    return 1 + steps(level - 1);
}

階乗も小さい問題の戻り値を受け取って掛ける仕組みで、たとえば3の階乗は 3 × (2 × (1 × 1)) と戻ります。フィボナッチは2つの呼び出しの戻り値を足します。入力が0以上なので、0と1の停止条件は m <= 1 にまとめて m を返せます。

2つの補助関数の宣言と、呼び出して文字列を作る処理は渡しています。書くのは各補助関数の停止条件と再帰の戻り値です。仮の return 0 を置き換えます。n は 0〜10、m は 0〜25 の整数です。

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. 数の前後の空白と区切りの半角スラッシュの位置を見本どおりに揃えること
9. ひな形の補助処理と出力整形を使い、2つの補助関数の停止条件と再帰の戻り値を書くこと
10. n は 0〜10、m は 0〜25 の整数です