Как правильно написать запоминание для фибоначи
Написал цикл фибоначи с помощью рекурсии. Подскажите, как для данной функции реализовать меморизацию? Все перепробовал ничего не помогает.
def fibonacci(n):
if n in (1, 2):
return 1
if n in (3,):
print(3,)
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))
Ответы (1 шт):
Автор решения: oleksandrigo
→ Ссылка
Просто добавь декоратор кеша
import functools
@functools.cache
def ...
Без декоратора можно так
M = {0: 0, 1: 1}
def fib(n):
if n in M:
return M[n]
M[n] = fib(n - 1) + fib(n - 2)
return M[n]