← Все уроки

Урок 12.8

Рекурсия с запоминанием

▶ Теория

Числа Фибоначчи по определению считаются рекурсией: каждая следующая — сумма двух предыдущих.

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Проверка даёт число n. Напишите fib с запоминанием в словарь memo из memo = {} наверху. Напечатайте fib(n) и memo: в словаре видно, какие числа пришлось считать и запомнить: все числа от 2 до n.

Подсказка

Запоминание — словарь снаружи функции.

Первым делом проверьте, нет ли n в memo, — тогда вернуть готовое. База — n < 2. Иначе посчитайте сумму двух предыдущих и сохраните её в memo, прежде чем вернуть.