Факторы ветвления
При работе с рекурсивными функциями иногда бывает нужно несколько раз вызвать ту же самую функцию с разными аргументами. Например, если бы мы вычисляли n-е число Фибоначчи с помощью рекурсивной функции, это могло бы выглядеть так:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Здесь для каждого значения
n совершается 2 рекурсивных вызова функции fib с аргументами n-1 и n-2.Задание — Рекурсивный Fibonacci
Посчитайте, сколько раз будет вызвана функция
fib при её выполнении.Входные данные
Во входных данных содержится одно целое число
n (0 ≤ n ≤ 20).Выходные данные
Программа должна вывести число вызовов функции
fib.Примеры
Вход | Выход |
0 | 1 |
1 | 1 |
2 | 3 |
5 | 15 |
6 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB