ブランチングファクター
再帰関数を扱うときに、引数を変えて同じ関数を複数回呼び出すのが有効な場合があります。たとえば、n 番目のフィボナッチ数を再帰的に計算すると考えてみましょう。すると、以下のようになるかもしれません。
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)ここでは、引数 n に対して、n-1 と n-2 を使って 2 回再帰呼び出しを行っています。
チャレンジ - 再帰的フィボナッチ
再帰的なフィボナッチ関数が呼び出される回数を数えてみましょう。
入力
入力には、単一の整数 n (0 ≤ n ≤ 20) が与えられます。
出力
プログラムは、fib 関数が呼び出された回数を出力してください。
例
Input | Output |
0 | 1 |
1 | 1 |
2 | 3 |
5 | 15 |
6 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB