Последовательность Фибоначчи
В этом упражнении вы реализуете последовательность Фибоначчи — одну из самых известных математических последовательностей, встречающуюся в природе повсеместно. Она выглядит так: «0, 1, 1, 2, 3, 5, 8…». Вам предстоит создать рекурсивную реализацию алгоритма, генерирующего эту последовательность.
Первые два числа равны 0 и 1, а каждое следующее является суммой двух предыдущих.
Последовательность можно определить рекурсивно как: \(fib(n)=fib(n-1)+fib(n-2)\), где \(fib(0)=0\) и \(fib(1)=1\), а \(n\) — это \(n\)-я позиция в последовательности.
На первом шаге вы реализуете последовательность Фибоначчи с помощью рекурсии. На втором шаге улучшите решение, применив динамическое программирование: результаты подзадач будут сохраняться в переменной cache.
Это упражнение является частью курса
Структуры данных и алгоритмы на Python
Интерактивное практическое упражнение
Попробуйте выполнить это упражнение, дополнив этот пример кода.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))