Branching factors
When dealing with recursive functions, it sometimes makes sense to call the current function several times with different arguments. For example, if we would calculate the
n-th Fibonacci number with a recursive function, that might look something like this:def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Here, for each argument
n, we make 2 recursive calls to the function fib with arguments n-1 and n-2.Challenge - Recursive Fibonacci
Count the number of times the recursive Fibonacci function is called.
Input
The input contains a single integer
n (0 ≤ n ≤ 20).Output
The program should print the number of times the
fib function was called.Examples
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