Рекурсия: функции, которые вызывают сами себя

Как функция решает задачу, вызывая себя для её меньшей части: базовый случай и рекурсивный шаг, стек вызовов и `RecursionError`, факториал, числа Фибоначчи, сумма цифр, рекурсивный двоичный поиск, вложенные списки и деревья папок — и когда лучше выбрать цикл или `lru_cache`.

  • Средний
  • 22 мин
  • 12 вопросов
  • Урок 11 из 66

В этом уроке ты узнаешь

  • Писать рекурсивную функцию с правильным базовым случаем и шагом, который к нему приближается
  • Объяснять, как растёт и уменьшается стек вызовов и откуда берётся RecursionError
  • Решать классические задачи рекурсивно: факториал, Фибоначчи, сумма цифр, двоичный поиск
  • Обрабатывать вложенные данные (списки, папки) и выбирать между рекурсией, циклом и lru_cache

В папке лежат файлы и другие папки, а в тех папках — снова файлы и папки. Как сосчитать все файлы, если неизвестно, насколько глубока вложенность? Цикл for должен заранее знать, по чему он проходит. Но у этой задачи есть красивое свойство: сосчитать файлы во вложенной папке — та же задача, только меньше. Функция, которая решает задачу, вызывая саму себя для её меньшей части, называется рекурсивной. В уроке «Функции» ты научился создавать и вызывать функции, а теперь функция будет вызывать сама себя.

РекурсияОпределение

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

Базовый случай и рекурсивный шаг

Самый простой пример — обратный отсчёт. countdown(3) печатает 3 и передаёт остальную работу — отсчёт от 2 — вызову countdown(2). Когда n доходит до 0, функция печатает Start! и останавливается: это базовый случай. Факториал устроен так же: чтобы найти 5!, нужен 4!, для 4! — 3! и так далее до 1! = 1.

n! = n · (n − 1)!0! = 1! = 1

Где

n
натуральное число
n!
произведение 1 · 2 · … · n

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

Python
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(4) = 4 · factorial(3)
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.

Стек вызововОпределение

Список начатых, но ещё не завершённых вызовов функций, упорядоченный по правилу «последним пришёл — первым ушёл». Верхний кадр выполняется сейчас, остальные ждут его результата.

↑ новый вызов кладётся сверхувозвратfactorial(1)базовый случай: вернёт 1factorial(2)ждёт: 2 · factorial(1)factorial(3)ждёт: 3 · factorial(2)print(factorial(3))программа ждёт результат126
Вызовы наращивают стек вверх, каждый return снимает верхний кадр.
Python
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:

Python
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 % 10 + S(n // 10)S(n) = n, if 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) = F(n − 1) + F(n − 2)F(0) = 0F(1) = 1

Где

F(n)
n-е число Фибоначчи

Нужны два базовых случая, потому что шаг смотрит на два члена назад.

Python
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]
4096 → 6 + 9 + 0 + 4 = 19; 987654321 → 9 + 8 + … + 1 = 45.

Примеры: предскажи результат

Задача

1) digit_sum(507); 2) fib(7); 3) сколько раз вызывается digit_sum для шестизначного числа?

Показать решениеСкрыть решение

Решение

1) 7 + digit_sum(50) = 7 + 0 + digit_sum(5) = 7 + 0 + 5 = 12.
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) = 2 · F(n + 1) − 1

Где

calls(n)
число вызовов наивной fib(n)

Для n = 20: F(21) = 10946, значит 2 · 10946 − 1 = 21891 вызов — ровно столько насчитает программа ниже.

Python
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, а не срезаем список, потому что каждый срез копировал бы элементы.

  1. Пустой диапазон

    Если lo > hi, значения нет: вернуть -1 (базовый случай).

  2. Средний элемент

    mid = (lo + hi) // 2; если items[mid] == target, вернуть mid (базовый случай).

  3. Правая половина

    Если items[mid] < target, искать в диапазоне [mid + 1..hi].

  4. Левая половина

    Иначе искать в диапазоне [lo..mid − 1].

Python
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
Для 10 элементов нужно не больше 4 шагов: диапазон сжимается 10 → 5 → 2 → 1. Для миллиона элементов хватит примерно 20 шагов, потому что 2²⁰ ≈ 10⁶.

Интерактив

Загрузка симуляции…
Посмотри, как двоичный поиск шаг за шагом делит диапазон пополам.

Рекурсивные данные: вложенные списки и деревья папок

Рекурсия выглядит естественнее всего, когда рекурсивны сами данные: списки внутри списков, папки внутри папок, комментарии с ответами, на которые тоже отвечают. Форма функции повторяет форму данных: для обычного элемента работает базовый случай, для вложенного функция вызывает себя снова.

Python
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 обрабатывает пустой список.

Дерево папок можно описать вложенными словарями: ключ — имя, число — размер файла в КБ, словарь — вложенная папка. Функция печатает дерево и возвращает его размер, а каждую вложенную папку обрабатывает та же функция уровнем глубже:

Python
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() отличает папку от файла. Программа сначала создаёт небольшую папку проекта (тоже рекурсивно), затем обходит её и сообщает число файлов и байтов в каждой папке:

Python
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
Python
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. Три вызова из начального кода не меняй.

Задание · Python
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 файлов.

Задание · Python
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; простые или очень глубокие последовательности → цикл.
Заметил ошибку или неточность в уроке?

Проверь себя

Вопросов: 12. Каждый правильный ответ приносит XP.

Вопрос 1 / 12

Вопрос 1 / 12. Какие две части обязательны для рекурсивной функции?