Рекурсия в Python: что это такое и как написать рекурсивную функцию

Рекурсия — это когда функция вызывает сама себя, каждый раз с задачей поменьше, пока задача не станет настолько простой, что ответ известен сразу. В Python у рекурсивной функции всегда две части: базовый случай, где вызовы прекращаются, и рекурсивный шаг, где функция обращается к себе с уменьшенными данными. Без базового случая программа упадёт с ошибкой RecursionError примерно через тысячу вызовов.

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

CheckroiПодборка курсов по Python568 курсов • 51 школаСравните цены, школы, программу и найдите выгодные предложения по обучениюСравнить→

Что такое рекурсия простыми словами

Представьте матрёшку. Чтобы найти самую маленькую куклу, вы открываете большую, внутри видите куклу поменьше и повторяете то же действие. Остановитесь вы, когда кукла не откроется. Это и есть рекурсия: одно и то же правило, применённое к уменьшенной копии задачи, плюс понятный момент остановки.

В программировании рекурсией называют приём, при котором функция обращается к самой себе. Такую функцию называют рекурсивной. Её ещё называют просто «функция, которая вызывает сама себя».

Компиляторы некоторых языков превращают хвостовую рекурсию в цикл, Python этого не делает. Почему, расскажем в разделе про глубину.

Как написать рекурсивную функцию в Python

Возьмём классику: факториал. Факториал числа 5 равен 5 × 4 × 3 × 2 × 1 = 120. Заметьте, что 5! = 5 × 4!, а 4! = 4 × 3!. Задача сама сводится к такой же, только на единицу меньше. Для рекурсии это идеальный случай.

1. Найдите базовый случай. Для факториала это n <= 1: ответ равен 1, считать ничего не нужно.
2. Сформулируйте рекурсивный шаг. Ответ для n выражается через ответ для n - 1: n * factorial(n - 1).
3. Проверьте, что шаг приближает к базовому случаю. Каждый вызов уменьшает n на единицу, значит, рано или поздно n дойдёт до 1.
4. Верните результат через return в обеих ветках.

def factorial(n):
    if n <= 1:          # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный шаг

print(factorial(5))
print(factorial(1))

Вывод:

120
1

Тот же шаблон работает со списками. Сумма списка равна первому элементу плюс сумма остальных, а сумма пустого списка равна нулю. Хвост списка берём срезом numbers[1:]:

def total(numbers):
    if not numbers:
        return 0
    return numbers[0] + total(numbers[1:])

print(total([4, 8, 15, 16, 23, 42]))
print(total([]))

Вывод:

108
0

На практике сумму считает встроенная sum(), про неё есть отдельная инструкция по суммированию списка. Здесь пример нужен, чтобы увидеть схему «базовый случай + шаг» на знакомых данных.

Как работает рекурсия: стек вызовов

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

Добавим в факториал печать с отступом, чтобы увидеть это своими глазами:

def factorial(n, depth=0):
    pad = "  " * depth
    print(f"{pad}вызов factorial({n})")
    if n <= 1:
        print(f"{pad}базовый случай, вернул 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) вернул {result}")
    return result

factorial(4)

Вывод:

вызов factorial(4)
  вызов factorial(3)
    вызов factorial(2)
      вызов factorial(1)
      базовый случай, вернул 1
    factorial(2) вернул 2
  factorial(3) вернул 6
factorial(4) вернул 24

Видно две фазы:

• Спуск. Вызовы складываются друг на друга: 4, 3, 2, 1. Ни одно умножение ещё не выполнено.
• Подъём. Базовый случай вернул 1, и кадры начинают закрываться в обратном порядке: 2 × 1, потом 3 × 2, потом 4 × 6.

Отсюда главное свойство рекурсии: каждый незавершённый вызов занимает память, пока не дождётся ответа снизу. Для факториала 4 это четыре кадра, для факториала 1500 их было бы полторы тысячи. В этот потолок и упираются рекурсивные программы на больших входных данных.

Примеры рекурсии в Python

Факториал хорош для объяснения, но в работе его считают циклом или math.factorial. Рекурсия нужна там, где данные сами вложены друг в друга и глубина заранее неизвестна.

Развернуть вложенный список

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

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, 3], [4, [5, [6, 7]]], 8]))

Вывод:

[1, 2, 3, 4, 5, 6, 7, 8]

Методы append() и extend() разобраны в статье про добавление элементов в список.

Обойти вложенный словарь или JSON

Ответ API обычно приходит в формате JSON: словари внутри списков внутри словарей. Посчитаем все ключи на всех уровнях заказа:

def count_keys(data):
    if isinstance(data, dict):
        return len(data) + sum(count_keys(v) for v in data.values())
    if isinstance(data, list):
        return sum(count_keys(v) for v in data)
    return 0

order = {
    "id": 17,
    "client": {"name": "Анна", "city": "Казань"},
    "items": [
        {"title": "Книга", "price": 890},
        {"title": "Лампа", "price": 2490, "options": {"color": "белый"}},
    ],
}
print(count_keys(order))

Вывод:

11

Три ключа верхнего уровня, два у клиента, два у книги, три у лампы и один в её опциях. Та же схема подходит для поиска значения по всему дереву или для замены всех цен разом.

Бинарный поиск

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

def binary_search(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1                      # не нашли
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    return binary_search(arr, target, lo, mid - 1)

nums = [3, 8, 12, 19, 27, 34, 41, 56]
print(binary_search(nums, 27))
print(binary_search(nums, 5))

Вывод:

4
-1

Число 27 стоит под индексом 4, числа 5 в списке нет. Для списка из миллиона элементов глубина такой рекурсии около 20 вызовов, так что лимит здесь не страшен.

Проверить слово на палиндром

Слово читается одинаково в обе стороны, если совпадают крайние буквы и середина тоже палиндром. Определение уже рекурсивное, осталось переписать его кодом:

def is_palindrome(s):
    if len(s) < 2:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome("шалаш"))
print(is_palindrome("казак"))
print(is_palindrome("питон"))

Вывод:

True
True
False

Глубина рекурсии и RecursionError

Python ограничивает число вложенных вызовов. Узнать лимит можно функцией sys.getrecursionlimit(). В документации модуля sys сказано, что лимит задаёт максимальную глубину стека интерпретатора и не даёт бесконечной рекурсии переполнить стек C и обрушить Python.

Если вы раньше не искали ничего в справке Python, посмотрите, как устроен сайт python.org и его документация: ответы про лимиты и исключения проще всего находить там.

import sys

print(sys.getrecursionlimit())

def countdown(n):
    return countdown(n - 1)   # базового случая нет

try:
    countdown(10)
except RecursionError as e:
    print(type(e).__name__, "-", e)

Вывод в Python 3.14:

1000
RecursionError - maximum recursion depth exceeded

Исключение RecursionError появилось в Python 3.5, раньше в этой ситуации падал обычный RuntimeError. Это указано в справке по встроенным исключениям.

Лимит можно поднять через sys.setrecursionlimit(5000). Документация предупреждает: максимально возможное значение зависит от платформы, а слишком высокий лимит может привести к падению интерпретатора. Если программе нужна глубина в десятки тысяч вызовов, надёжнее переписать её циклом.

Почему Python не превращает хвостовую рекурсию в цикл, как это делают некоторые функциональные языки? Создатель языка Гвидо ван Россум объяснил это в 2009 году в записи блога: такая оптимизация несовместима с понятными трассировками ошибок, а Python по умолчанию должен максимально помогать при отладке. Поэтому даже правильно оформленная хвостовая рекурсия тратит по кадру стека на вызов.

Рекурсия или цикл

Любую рекурсию можно переписать циклом, и наоборот. Вот тот же факториал через цикл while:

def factorial(n):
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

print(factorial(5))
print(len(str(factorial(1500))))

Вывод:

120
4115

Цикл спокойно посчитал факториал 1500, в нём 4115 цифр. Рекурсивная версия на том же числе упирается в лимит:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

try:
    factorial(1500)
except RecursionError as e:
    print("RecursionError:", e)

Вывод:

RecursionError: maximum recursion depth exceeded

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

Когда рекурсия становится медленной

Числа Фибоначчи часто приводят в учебниках как пример рекурсии, и это заодно ловушка. Каждое число равно сумме двух предыдущих, и прямая рекурсия считает одни и те же значения снова и снова. Добавим счётчик вызовов:

calls = 0

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

print(fib(25), calls)

Вывод:

75025 242785

Чтобы получить 25-е число, функция вызвала себя 242 785 раз. Исправляет это кеш: декоратор @cache из модуля functools запоминает уже посчитанные ответы. По документации functools, он появился в Python 3.9 и работает как lru_cache(maxsize=None).

from functools import cache

calls = 0

@cache
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(25), calls)
print(fib(300))

Вывод:

75025 26
222232244629420445529739893461909967206666939096499764990979600

Вызовов стало 26 вместо 242 785, а 300-е число считается мгновенно. Если у вас Python старше 3.9, используйте @lru_cache(maxsize=None), результат тот же.

Канал основателя Checkroi Вани БуявцаЗабирайте промпты и обучение по нейросетям в моём Телеграм-каналеБольше 3 700 человек уже применяют Claude Code, ChatGPT и другие нейросети в работе, учёбе, бизнесе и жизниПерейти в канал→

Частые ошибки в рекурсивных функциях

Нет базового случая

Функция countdown из раздела про глубину вызывает себя, пока Python не остановит её на тысячном кадре. Симптом: RecursionError: maximum recursion depth exceeded сразу при первом запуске.

Решение: прежде чем писать рекурсивный шаг, напишите if с условием остановки и return.

Базовый случай недостижим

Условие остановки есть, но данные его проскакивают. Факториал с проверкой n == 1 на нуле уходит в минус:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

try:
    print(factorial(0))
except RecursionError as e:
    print("RecursionError:", e)

Вывод:

RecursionError: maximum recursion depth exceeded

Решение: ставьте условие с запасом (n <= 1 вместо n == 1) и проверяйте функцию на крайних входах: 0, отрицательное число, пустой список.

Забыли return перед рекурсивным вызовом

Вызов выполняется, но результат никуда не уходит, и функция возвращает None. На следующем уровне вверх сложение с None ломает программу:

def total(numbers):
    if not numbers:
        return 0
    numbers[0] + total(numbers[1:])   # забыли return

print(total([1, 2, 3]))

Последняя строка трассировки:

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

Решение: если в сообщении об ошибке встречается NoneType, первым делом проверьте, что у каждой ветки рекурсивной функции есть return.

Изменяемое значение по умолчанию

Накопитель результата часто передают параметром. Если сделать его пустым списком по умолчанию, список создастся один раз на всю программу и будет копить данные между вызовами:

def collect(items, acc=[]):
    for item in items:
        if isinstance(item, list):
            collect(item, acc)
        else:
            acc.append(item)
    return acc

print(collect([1, [2, 3]]))
print(collect([4]))

Вывод:

[1, 2, 3]
[1, 2, 3, 4]

Второй вызов с [4] вернул и старые элементы. Решение: по умолчанию передавайте None, а список создавайте внутри функции.

def collect(items, acc=None):
    if acc is None:
        acc = []
    for item in items:
        if isinstance(item, list):
            collect(item, acc)
        else:
            acc.append(item)
    return acc

print(collect([1, [2, 3]]))
print(collect([4]))

Вывод:

[1, 2, 3]
[4]

Повторные вычисления

Функция с двумя рекурсивными вызовами на каждом шаге, как Фибоначчи выше, растёт по числу вызовов лавинообразно. Решение: кеш через @cache или переписать задачу циклом, который идёт снизу вверх.

Где освоить Python системно

Рекурсия обычно идёт в учебных программах сразу после функций, и закрепить её проще на задачах: посмотрите 30 задач по Python для начинающих и попробуйте решить часть из них рекурсивно. Если интересно, как рекурсия становится основным способом писать программы, загляните в разбор языков Prolog и Lisp: циклов в привычном виде там почти нет.

Алгоритмы, структуры данных и рекурсию спрашивают на собеседованиях Python-разработчиков, об этом подробнее в плане, как стать Python-разработчиком. Если нужна программа с наставником и проверкой домашних заданий, сравните курсы по Python разных школ по цене и длительности. Вот пять из них:

Курс	Школа	Стоимость со скидкой	В рассрочку	Длитель­ность	Обзор курса от Checkroi
Профессия «Python-разработчик» Перейти на сайт курса	Skillbox	157 335 ₽	5987 ₽/мес.	10 месяцев	Обзор курса
Fullstack-разработчик на Python Перейти на сайт курса	Нетология	137 000 ₽	7125 ₽/мес.	21 месяц	Обзор курса
ДО Профессия Python-разработчик Перейти на сайт курса	GeekBrains	149 001 ₽	3167 ₽/мес.	10 месяцев	Обзор курса
Автоматизированное тестирование на Python Перейти на сайт курса	Skillbox	122 226 ₽	4108 ₽/мес.	9 месяцев	Обзор курса
Профессия Python-разработчик Перейти на сайт курса	SkillFactory	140 040 ₽	4279 ₽/мес.	10 месяцев	Обзор курса

• 

  Профессия «Python-разработчик»

  Skillbox157 335 ₽5987 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор
• 

  Fullstack-разработчик на Python

  Нетология137 000 ₽7125 ₽/мес21 месяц
  Перейти на сайт курсаОбзор
• 

  ДО Профессия Python-разработчик

  GeekBrains149 001 ₽3167 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор
• 

  Автоматизированное тестирование на Python

  Skillbox122 226 ₽4108 ₽/мес9 месяцев
  Перейти на сайт курсаОбзор
• 

  Профессия Python-разработчик

  SkillFactory140 040 ₽4279 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор

Больше программ — в полном каталоге курсов по Python