Рекурсивные функции: вычисление значений и подсчёт вызовов

Функция называется рекурсивной, если в своём теле она вызывает саму себя. У любой корректной рекурсии есть две части:

• база — значения аргумента, для которых ответ известен сразу, без новых вызовов;
• шаг — выражение, которое сводит вычисление к более «простым» значениям (с меньшим аргументом).

Если базы нет или шаг не приближает аргумент к базе, функция вызывает себя бесконечно, и программа завершается ошибкой переполнения стека.

Что просят в задаче № 16

Обычно дают определение функции в виде двух-трёх строк, например:

• F(n) = n при n ≤ 2;
• F(n) = F(n − 1) + F(n − 2) + 1 при n > 2;

и просят найти значение F(n) при большом n, число вызовов или значение выражения, составленного из нескольких вызовов. Считать вручную до конца почти никогда не нужно: пишем программу.

Вычисление значения

Первое, что стоит сделать, — переписать определение один к одному.

import sys
from functools import lru_cache

sys.setrecursionlimit(10000)      # глубина по умолчанию около 1000

@lru_cache(None)                  # запоминаем уже вычисленные значения
def F(n):
    if n <= 2:
        return n
    return F(n - 1) + F(n - 2) + 1

print([F(i) for i in range(1, 8)])   # 1 2 4 7 12 20 33
print(F(30))

Декоратор lru_cache запоминает результат для каждого аргумента. Без него число вызовов растёт как показательная функция от n, и уже F(40) вычисляется очень долго. С запоминанием каждое значение считается один раз.

Проверьте себя на малых значениях: F(3) = F(2) + F(1) + 1 = 2 + 1 + 1 = 4, F(4) = 4 + 2 + 1 = 7. Если ваша программа даёт другое число, значит, определение переписано неверно.

Как сосчитать количество вызовов

Если спрашивают, сколько раз была вызвана функция (или сколько раз выполнилась какая-то строка), счётчик заводят отдельно и не используют запоминание: иначе повторные вызовы пропадут.

calls = 0

def G(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return G(n - 1) + G(n - 2)

G(5)
print(calls)   # 15

Для G(5) получается 15 вызовов: G(5), потом G(4) и G(3) и так далее. Число вызовов можно сосчитать и самой рекуррентой: C(n) = 1 + C(n − 1) + C(n − 2) с базой C(0) = C(1) = 1.

Что печатает процедура

Бывает, что функция ничего не возвращает, а печатает. Тогда важен порядок действий внутри тела:

def H(n):
    if n > 0:
        print(n, end=' ')
        H(n - 1)
        print(n, end=' ')

H(3)      # 3 2 1 1 2 3

Первая печать выполняется до вызова вложенной процедуры (на «спуске»), вторая — после возврата (на «подъёме»). Поэтому числа сначала убывают, а потом возрастают.

Типичные ошибки

• Запоминание включили там, где нужно считать вызовы: счётчик показывает слишком мало.
• Забыли поднять предел глубины рекурсии: для аргументов в несколько тысяч программа падает с RecursionError.
• Перепутали условие базы: n < 2 и n <= 2 дают разные значения.
• Для функций с несколькими аргументами запоминание всё равно работает, но убедитесь, что аргументы — числа или кортежи, а не списки.

Если аргумент очень большой, лучше заменить рекурсию циклом, в котором значения хранятся в массиве от базы к нужному n: это тот же приём, что в статье «Подсчёт путей и динамическое программирование».