База и шаг
Рекурсивная функция — функция, которая в своём теле вызывает саму себя. Чтобы вызовы не шли бесконечно, нужны две части.
Шаг — сведение задачи к такой же, но меньшей (F(n) выражается через F(n − 1)).
def F(n):
if n == 1: # база
return 1
return 2 * F(n - 1) + 1 # шаг
print(F(5)) # 31Проверь себя. F(1) = 1, F(n) = 2·F(n − 1) + 1. Чему равно F(5)?
Ответ: 31
Как вычисляют значение: спуск и подъём
Чтобы найти F(5), компьютер вызывает F(4), тот — F(3) и так до базы F(1). Затем значения возвращаются наверх: F(2) = 3, F(3) = 7, F(4) = 15, F(5) = 31.
На бумаге проще идти от малых n вверх: заполните таблицу значений F(1), F(2), F(3), … по формуле шага.
Пример (ЕГЭ-16). F(n) = n при n ≤ 10; F(n) = n + F(n − 3) при n > 10. Найти F(20): F(20) = 20 + F(17) = 20 + 17 + F(14) = 37 + 14 + F(11) = 51 + 11 + F(8) = 62 + 8 = 70.
Порядок печати и дерево вызовов
Печать до рекурсивного вызова выполняется по пути вниз, после — на пути вверх.
def f(n):
if n > 0:
print(n, end='')
f(n - 1)
print(n, end='')
f(3) # 321123Если функция вызывает себя дважды (как числа Фибоначчи), вызовы образуют дерево. Число вызовов: G(1) = G(2) = 1 вызов; G(n) = 1 + G(n − 1) + G(n − 2).
Пример. Функция def F(n): return 1 if n < 3 else F(n − 1) + F(n − 2). Число вызовов при F(5): G(3) = 3, G(4) = 5, G(5) = 1 + 5 + 3 = 9.
Python: запоминание и глубина
У дерева вызовов много одинаковых поддеревьев (F(3) считается дважды и более). Декоратор lru_cache запоминает уже найденные значения и делает вычисление быстрым.
from functools import lru_cache
import sys
sys.setrecursionlimit(100000) # глубина по умолчанию около 1000
@lru_cache(None)
def F(n):
if n <= 10:
return n
return n + F(n - 3)
print(F(2024) - F(2021))Проверь себя. Функция считает F(n) = F(n − 1) + F(n − 2) при n ≥ 3, F(1) = F(2) = 1. Сколько вызовов будет сделано при вычислении F(5) без запоминания?
Ответ: 9