Послідовність Фібоначчі
У цій вправі ви реалізуєте послідовність Фібоначчі, яку часто спостерігають у природі. Вона виглядає так: «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))