В папке лежат файлы и другие папки, а в тех папках — снова файлы и папки. Как сосчитать все файлы, если неизвестно, насколько глубока вложенность? Цикл for должен заранее знать, по чему он проходит. Но у этой задачи есть красивое свойство: сосчитать файлы во вложенной папке — та же задача, только меньше. Функция, которая решает задачу, вызывая саму себя для её меньшей части, называется рекурсивной. В уроке «Функции» ты научился создавать и вызывать функции, а теперь функция будет вызывать сама себя.
РекурсияОпределение
Способ решения, при котором функция вызывает саму себя с меньшими или более простыми входными данными. У каждой рекурсивной функции две части: базовый случай, на который ответ даётся сразу, без нового вызова, и рекурсивный шаг, который уменьшает задачу и снова вызывает функцию.
Базовый случай и рекурсивный шаг
Самый простой пример — обратный отсчёт. countdown(3) печатает 3 и передаёт остальную работу — отсчёт от 2 — вызову countdown(2). Когда n доходит до 0, функция печатает Start! и останавливается: это базовый случай. Факториал устроен так же: чтобы найти 5!, нужен 4!, для 4! — 3! и так далее до 1! = 1.
Где
- n
- натуральное число
- n!
- произведение 1 · 2 · … · n
В правиле та же операция повторяется для меньшего числа (рекурсивный шаг), и есть значение, известное без вычислений (базовый случай).
def countdown(n):
if n == 0: # base case
print('Start!')
return
print(n)
countdown(n - 1) # recursive step
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
countdown(3)
print(factorial(5), factorial(10))Ожидаемый результат
3 2 1 Start! 120 3628800
countdown ничего не возвращает, только печатает; factorial передаёт результат вызывающему коду через return.Пример: раскрываем factorial(4)
Задача
Не запуская код, вычисли factorial(4) по шагам и скажи, сколько будет вызовов.
Показать решениеСкрыть решение
Решение
factorial(3) = 3 · factorial(2)
factorial(2) = 2 · factorial(1)
factorial(1) = 1 — базовый случай, нового вызова нет.
Теперь результаты идут обратно: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.
Всего 4 вызова: по одному для n = 4, 3, 2, 1.
Чтобы читать дальше, зарегистрируйся бесплатно
Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.
Стек вызовов и RecursionError
Как одна функция может выполняться несколько раз одновременно? Каждый вызов получает свой кадр (frame): небольшую область памяти со своими параметрами и локальными переменными. Кадры хранятся в стеке вызовов: новый вызов кладётся наверх, а когда вызов завершается через return, его кадр снимается и результат передаётся кадру ниже. Пока работает factorial(1), вызовы factorial(4), factorial(3) и factorial(2) ждут в стеке, и у каждого свой n.
Стек вызововОпределение
Список начатых, но ещё не завершённых вызовов функций, упорядоченный по правилу «последним пришёл — первым ушёл». Верхний кадр выполняется сейчас, остальные ждут его результата.
return снимает верхний кадр.def factorial(n, depth=0):
pad = ' ' * depth
print(f'{pad}factorial({n}) called')
if n <= 1:
result = 1
else:
result = n * factorial(n - 1, depth + 1)
print(f'{pad}factorial({n}) returns {result}')
return result
print('answer:', factorial(4))Ожидаемый результат
factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6
factorial(4) returns 24
answer: 24Стек не бесконечен. По умолчанию CPython допускает около 1000 вложенных вызовов (sys.getrecursionlimit() показывает предел). Если базового случая нет или до него никогда не доходит, вызовы не прекращаются, предел превышается, и Python останавливает программу с ошибкой RecursionError: maximum recursion depth exceeded. Ниже у broken базового случая нет вовсе, а у also_broken он есть, но при нечётном n шаг n − 2 перепрыгивает через 0:
def broken(n):
return n * broken(n - 1) # no base case
def also_broken(n):
if n == 0:
return 0
return n + also_broken(n - 2) # an odd n jumps over 0
for func, arg in ((broken, 5), (also_broken, 6), (also_broken, 7)):
try:
print(func.__name__, arg, '->', func(arg))
except RecursionError:
print(func.__name__, arg, '-> RecursionError')Ожидаемый результат
broken 5 -> RecursionError also_broken 6 -> 12 also_broken 7 -> RecursionError
also_broken(6) = 6 + 4 + 2 + 0 = 12. С 7 получается 7, 5, 3, 1, −1, … — до 0 дело не доходит. Надёжнее был бы базовый случай if n <= 0.забыт `return`
def digit_sum(n):
if n < 10:
return n
n % 10 + digit_sum(n // 10)правильно
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)return вызов digit_sum(25) возвращает None, а для 2026 программа даже падает: уровнем выше Python должен вычислить 2 + None и выдаёт TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'.Классические задачи: сумма цифр, Фибоначчи, двоичный поиск
Многие определения в математике уже рекурсивны. Сумма цифр числа — это его последняя цифра (n % 10) плюс сумма цифр числа без этой цифры (n // 10); у однозначного числа сумма цифр равна самому числу. Числа Фибоначчи определяются через два предыдущих члена последовательности.
Где
- S(n)
- сумма цифр числа n
- n % 10
- остаток от деления на 10 — последняя цифра
- n // 10
- целочисленное деление — отбрасывает последнюю цифру
S(2026) = 6 + S(202) = 6 + 2 + S(20) = 6 + 2 + 0 + S(2) = 10.
Где
- F(n)
- n-е число Фибоначчи
Нужны два базовых случая, потому что шаг смотрит на два члена назад.
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(digit_sum(2026), digit_sum(4096), digit_sum(987654321))
print([fib(n) for n in range(12)])Ожидаемый результат
10 19 45 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Примеры: предскажи результат
Задача
1) digit_sum(507); 2) fib(7); 3) сколько раз вызывается digit_sum для шестизначного числа?
Показать решениеСкрыть решение
Решение
2) F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, F(7) = 13.
3) Каждый вызов отбрасывает одну цифру, пока не останется одна: 6 вызовов для шестизначного числа (k цифр — k вызовов).
Функция Фибоначчи короткая, но очень медленная. Каждый вызов делает ещё два вызова, и одни и те же значения вычисляются снова и снова: fib(5) дважды вычисляет fib(3) и трижды — fib(2). Число вызовов растёт почти так же быстро, как сами числа Фибоначчи:
Где
- calls(n)
- число вызовов наивной
fib(n)
Для n = 20: F(21) = 10946, значит 2 · 10946 − 1 = 21891 вызов — ровно столько насчитает программа ниже.
from functools import lru_cache
calls = 0
def fib(n):
global calls
calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)
for n in (10, 20, 25):
calls = 0
value = fib(n)
print(f'fib({n}) = {value}: {calls} calls')
@lru_cache(maxsize=None)
def fib_cached(n):
return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)
def fib_loop(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_cached(90), fib_loop(90), fib_cached.cache_info().misses)Ожидаемый результат
fib(10) = 55: 177 calls fib(20) = 6765: 21891 calls fib(25) = 75025: 242785 calls 2880067194370816120 2880067194370816120 91
lru_cache запоминает каждый результат, поэтому fib_cached(90) выполняет всего 91 настоящее вычисление (misses) — по одному для каждого n от 0 до 90. Вариант с циклом хранит только два последних числа и вообще не нуждается в стеке. Как устроен lru_cache, объясняется в уроке «Декораторы и замыкания».Двоичный поиск находит значение в отсортированном списке, на каждом шаге деля диапазон пополам, — каждый шаг решает ту же задачу на половине данных. Мы передаём границы lo и hi, а не срезаем список, потому что каждый срез копировал бы элементы.
Пустой диапазон
Если
lo > hi, значения нет: вернуть-1(базовый случай).Средний элемент
mid = (lo + hi) // 2; еслиitems[mid] == target, вернутьmid(базовый случай).Правая половина
Если
items[mid] < target, искать в диапазоне[mid + 1..hi].Левая половина
Иначе искать в диапазоне
[lo..mid − 1].
def binary_search(items, target, lo=0, hi=None):
if hi is None:
hi = len(items) - 1
if lo > hi: # base case: nothing left
return -1
mid = (lo + hi) // 2
print(f' range [{lo}..{hi}], items[{mid}] = {items[mid]}')
if items[mid] == target: # base case: found
return mid
if items[mid] < target:
return binary_search(items, target, mid + 1, hi)
return binary_search(items, target, lo, mid - 1)
scores = [12, 25, 31, 47, 58, 63, 77, 84, 90, 96]
print('77 at index', binary_search(scores, 77))
print('50 at index', binary_search(scores, 50))Ожидаемый результат
range [0..9], items[4] = 58 range [5..9], items[7] = 84 range [5..6], items[5] = 63 range [6..6], items[6] = 77 77 at index 6 range [0..9], items[4] = 58 range [0..3], items[1] = 25 range [2..3], items[2] = 31 range [3..3], items[3] = 47 50 at index -1
Интерактив
Рекурсивные данные: вложенные списки и деревья папок
Рекурсия выглядит естественнее всего, когда рекурсивны сами данные: списки внутри списков, папки внутри папок, комментарии с ответами, на которые тоже отвечают. Форма функции повторяет форму данных: для обычного элемента работает базовый случай, для вложенного функция вызывает себя снова.
def total(data):
result = 0
for item in data:
if isinstance(item, list):
result += total(item) # a smaller list of the same kind
else:
result += item
return result
def depth(data):
if not isinstance(data, list):
return 0
return 1 + max((depth(x) for x in data), default=0)
expenses = [120, [30, 45, [5, 5]], 60, [[10], 20]]
print(total(expenses), depth(expenses))
print(total([]), depth([]), depth(7))Ожидаемый результат
295 3 0 1 0
total складывает все числа на любой глубине: 120 + 30 + 45 + 5 + 5 + 60 + 10 + 20 = 295. depth считает уровни скобок; default=0 обрабатывает пустой список.Дерево папок можно описать вложенными словарями: ключ — имя, число — размер файла в КБ, словарь — вложенная папка. Функция печатает дерево и возвращает его размер, а каждую вложенную папку обрабатывает та же функция уровнем глубже:
tree = {
'school': {
'math': {'algebra.pdf': 320, 'geometry.pdf': 410},
'photos': {'trip': {'baku.jpg': 2048, 'quba.jpg': 1730}, 'class.png': 960},
'plan.txt': 12,
}
}
def show(folder, indent=0):
size = 0
for name, content in folder.items():
if isinstance(content, dict): # a folder: recurse
print(' ' * indent + name + '/')
size += show(content, indent + 1)
else: # a file: base case
print(' ' * indent + f'{name} ({content} KB)')
size += content
return size
print('Total:', show(tree), 'KB')Ожидаемый результат
school/
math/
algebra.pdf (320 KB)
geometry.pdf (410 KB)
photos/
trip/
baku.jpg (2048 KB)
quba.jpg (1730 KB)
class.png (960 KB)
plan.txt (12 KB)
Total: 5480 KBТеперь настоящий диск. В модуле pathlib метод Path.iterdir() перечисляет содержимое папки, а is_dir() отличает папку от файла. Программа сначала создаёт небольшую папку проекта (тоже рекурсивно), затем обходит её и сообщает число файлов и байтов в каждой папке:
from pathlib import Path
def make(folder, spec):
for name, content in spec.items():
path = folder / name
if isinstance(content, dict):
path.mkdir()
make(path, content)
else:
path.write_text('x' * content)
def report(folder, indent=0):
files, size = 0, 0
for path in sorted(folder.iterdir()):
if path.is_dir():
f, s = report(path, indent + 1)
print(' ' * indent + f'{path.name}/ files={f}, bytes={s}')
files, size = files + f, size + s
else:
files, size = files + 1, size + path.stat().st_size
return files, size
root = Path('project')
root.mkdir()
make(root, {'docs': {'a.txt': 120, 'b.txt': 80, 'old': {'c.txt': 300}},
'src': {'main.py': 450}, 'readme.md': 50})
print(report(root))
print(sum(p.stat().st_size for p in root.rglob('*') if p.is_file()))Ожидаемый результат
old/ files=1, bytes=300 docs/ files=3, bytes=500 src/ files=1, bytes=450 (5, 1000) 1000
rglob('*') обходит дерево за тебя и даёт те же 1000 байт: в реальных скриптах есть готовые rglob и os.walk, но внутри они делают ровно это.Рекурсия или цикл?
Любую рекурсивную функцию можно переписать циклом (при необходимости — со своим списком-стеком), и наоборот. Что выбрать, зависит от формы задачи:
| Ситуация | Лучший выбор | Почему |
|---|---|---|
| простая последовательность: сумма 1…n, факториал, отсчёт | цикл | нет стека и предела глубины, обычно быстрее |
| древовидные данные: вложенные списки, папки, JSON, HTML | рекурсия | код повторяет форму данных |
| «разделяй и властвуй»: двоичный поиск, сортировка слиянием, быстрая сортировка | рекурсия | глубина всего около log₂ n |
| одни и те же подзадачи снова и снова (Фибоначчи) | рекурсия + lru_cache или цикл | каждое значение вычисляется один раз |
| глубина может доходить до тысяч уровней | цикл с явным стеком | нет RecursionError |
def sum_rec(n):
return 0 if n == 0 else n + sum_rec(n - 1)
def sum_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
print(sum_rec(100), sum_loop(100))
try:
print(sum_rec(100_000))
except RecursionError:
print('sum_rec(100000): RecursionError')
print(sum_loop(100_000))Ожидаемый результат
5050 5050 sum_rec(100000): RecursionError 5000050000
sum_rec(100000) требует 100 000 кадров и падает, а циклу они не нужны вовсе. Python не оптимизирует хвостовую рекурсию, так что переписать функцию в другой рекурсивной форме тоже не поможет.Задание
Напиши рекурсивную функцию power(x, n): xⁿ = x · xⁿ⁻¹, x⁰ = 1 (n — целое число ≥ 0). Не используй оператор ** и pow. Три вызова из начального кода не меняй.
def power(x, n):
# base case: n == 0
# recursive step: x * power(x, n - 1)
pass
print(power(2, 10))
print(power(3, 4))
print(power(5, 0))Ожидаемый результат
1024 81 1
Задание
Функция count_files(folder) должна возвращать число файлов во вложенном словаре: ключ со значением-словарём — это вложенная папка, ключ со значением-числом — файл. В пустой папке 0 файлов.
tree = {
'docs': {'cv.pdf': 120, 'letters': {'a.txt': 4, 'b.txt': 6}},
'music': {},
'photo.jpg': 900,
}
def count_files(folder):
# a dict value is a subfolder, a number is a file
pass
print(count_files(tree))
print(count_files(tree['docs']))
print(count_files(tree['music']))Ожидаемый результат
4 3 0
Запомни
- Рекурсивная функция вызывает себя для меньшего входа; ей нужны базовый случай и шаг, который действительно к нему приближает.
- Каждый вызов получает свой кадр в стеке вызовов; результаты возвращаются в порядке, обратном вызовам.
- Без достижимого базового случая стек переполняется:
RecursionError(в CPython по умолчанию около 1000 уровней). Шаг безreturnдаётNone. - Рекурсия подходит для древовидных данных и задач «разделяй и властвуй»: вложенные списки, деревья папок, двоичный поиск.
- Повторяющиеся подзадачи →
functools.lru_cache; простые или очень глубокие последовательности → цикл.