フィボナッチ数（再帰）
フィボナッチ数は、直前の 2 つを足して次を作る数列です。0, 1, 1, 2, 3, 5, 8, 13 と続きます。前回と違うのは、1 段降りるときに 2 か所へ枝分かれすることです。枝分かれしても止まるのはなぜか、そして何が代償になるのかを見ていきます。
2 ずつ減らすと、止まる場所を飛び越える
引数を 2 ずつ減らす再帰を書いてみます。
Python
def skip(n):
if n == 0:
return 0
return skip(n - 2)skip(4) は 4, 2, 0 と降りて止まります。ところが skip(5) は 5, 3, 1, -1, -3 と進み、0 の横を素通りして止まりません。1 ずつ減らしていたときには起きなかった事故です。
飛び越えが起きるのは、止まる条件をぴったり一致で書いているからです。n <= 0 のように「それ以下」で止めておけば、どこから来ても必ず引っかかります。フィボナッチは 1 段降りるときに 1 減る道と 2 減る道の両方を通るので、この書き方の差がそのまま効いてきます。
枝が 2 本でも、深さは変わらない
自分自身を 2 回呼ぶ関数を動かしてみます。
Python
def branch(n):
if n == 0:
return
branch(n - 1)
branch(n - 1)これはきちんと止まります。どちらの枝も n が 1 ずつ減るので、3 段降りれば必ず 0 に着くからです。枝が何本あろうと、確かめることは前回と同じで、止まる条件があるかと、引数が縮んでいるかの 2 つだけです。
深さも変わりません。branch(3) は 3 段しか降りません。
同じ引数が、何度も戻ってくる
増えるのは呼び出しの回数のほうです。何回呼ばれたかを数えてみます。
Python
count = 0
def branch(n):
global count
count += 1
if n == 0:
return
branch(n - 1)
branch(n - 1)
branch(3)
print(count) # 15段ごとに 1, 2, 4, 8 と倍になり、合わせて 15 回です。深さは 3 段のままなのに、呼び出しの総数は段が 1 つ増えるたびに倍になります。
枝分かれする再帰の厄介なところは、同じ引数の計算を何度もやり直す点にもあります。フィボナッチを素直に再帰で書くと、5 を求める途中で 3 の計算が 2 回、2 の計算が 3 回走ります。左の枝で一度計算した答えを、右の枝がまた一から計算し直しているからです。
そのぶん、n が 1 増えるごとに呼び出し数がおよそ 1.6 倍になります。n が 30 くらいまでは一瞬ですが、40 を超えたあたりから待たされるのが体感できるようになります。同じ再帰の形でも、1 本しか呼ばない関数とはまるで話が違う、ということです。
正しく止まることと、現実的な時間で終わることは別の話です。今回のテストは
nが小さい範囲しか試さないので、素直に書いて構いません。
要件
- 関数
fib(n)を実装し、整数値を返す - for / while を使わず、必ず再帰で実装する
- n <= 1 の場合は n をそのまま返す (2 つの基底ケースをまとめる)
入出力例
fib(0) → 0
fib(1) → 1
fib(2) → 1
fib(6) → 8
fib(10) → 55
fib(15) → 610ヒント
