Рекурсия в Python: как работает, когда применять, примеры

Q: Что дальше?

Следующий урок посвящён функциям map(), filter() и reduce(), мощным инструментам функционального программирования в Python. Вы научитесь преобразовывать, фильтровать и объединять коллекции данных в одну строку кода.

Средний25 min6 упр.85 XP

Этот урок переведён с английского оригинала.Read in English Leer en español Сообщить об ошибке в переводе

Перед началом

Функции в Python: создание, вызов и возвращаемые значения

0/6 упр.

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

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

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

Что такое рекурсия?

Рекурсия возникает, когда функция вызывает саму себя. Вот и всё определение. Но зачем функции вообще вызывать саму себя?

Возьмём обратный отсчёт от 5. Процесс можно описать так: «Чтобы отсчитать от N, назовите N, а затем отсчитайте от N минус 1. Остановитесь, когда дойдёте до 0». Это рекурсивное описание: инструкция ссылается сама на себя.

Простой рекурсивный обратный отсчёт

def countdown(n):

if n == 0:

print("Go!")

return

print(n)

countdown(n - 1)

countdown(5)

Вывод

5
4
3
2
1
Go!

Функция countdown(5) выводит 5, а затем вызывает countdown(4). Та выводит 4 и вызывает countdown(3). Так продолжается, пока countdown(0) не выведет «Go!» и не остановится. Больше вызовов нет.

У каждой рекурсивной функции есть две обязательные части. Если не хватает хотя бы одной, функция будет работать вечно (или пока Python её не остановит).

Базовый случай: когда остановиться

Базовый случай задаёт условие, при котором рекурсия останавливается. Это самая маленькая матрёшка, та, что не открывается. Без базового случая функция вызывает себя бесконечно.

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

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

def countdown(n):

# BASE CASE - the stopping condition

if n == 0:

print("Go!")

return

# RECURSIVE CASE - do work, then call with smaller input

print(n)

countdown(n - 1)

countdown(3)

Вывод

3
2
1
Go!

Полезное правило: всегда пишите базовый случай первым. Затем пишите рекурсивный случай, который к нему приближается. Такой порядок не даст вам случайно забыть условие выхода.

Как работает стек вызовов

Когда функция вызывает саму себя, Python не забывает, где он был. Он использует стек вызовов: стопку «кадров» (frames), где каждый кадр помнит локальные переменные функции и место, с которого нужно продолжить работу.

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

Стек вызовов в действии

def factorial(n):

print(f" Calling factorial({n})")

if n <= 1:

print(f" Base case! factorial({n}) = 1")

return 1

result = n * factorial(n - 1)

print(f" factorial({n}) = {n} * factorial({n-1}) = {result}")

return result

print("Result:", factorial(5))

Вывод

  Calling factorial(5)
  Calling factorial(4)
  Calling factorial(3)
  Calling factorial(2)
  Calling factorial(1)
  Base case! factorial(1) = 1
  factorial(2) = 2 * factorial(1) = 2
  factorial(3) = 3 * factorial(2) = 6
  factorial(4) = 4 * factorial(3) = 24
  factorial(5) = 5 * factorial(4) = 120
Result: 120

Обратите внимание, как сообщения «Calling» уходят всё глубже, а затем результаты всплывают обратно. Стек вызовов растёт, пока вызовы уходят внутрь, и уменьшается, пока результаты возвращаются наружу. Этот ритм «туда и обратно» и есть сердцебиение рекурсии.

Классические примеры рекурсии

Факториал

Факториал числа N (записывается как N!) равен произведению N на все положительные целые числа меньше него. Например, 5! = 5 x 4 x 3 x 2 x 1 = 120.

Факториал рекурсивен по своей природе: 5! = 5 x 4!, а 4! = 4 x 3! и так далее. Базовый случай: 1! = 1.

Факториал с помощью рекурсии

def factorial(n):

if n <= 1: # Base case

return 1

return n * factorial(n - 1) # Recursive case

print(factorial(1)) # 1

print(factorial(5)) # 120

print(factorial(10)) # 3628800

Вывод

1
120
3628800

Сумма элементов списка

Вот ещё один шаблон: чтобы рекурсивно найти сумму списка, прибавьте первый элемент к сумме остальных.

Рекурсивная сумма элементов списка

def sum_list(numbers):

if len(numbers) == 0: # Base case: empty list

return 0

return numbers[0] + sum_list(numbers[1:]) # First + sum of rest

print(sum_list([1, 2, 3, 4, 5])) # 15

print(sum_list([10])) # 10

print(sum_list([])) # 0

Вывод

15
10
0

Шаблон такой: обработать базовый случай (для пустого списка вернуть 0), а затем разбить задачу на «первый элемент» плюс «рекурсивный вызов для остальных». Этот шаблон подходит для многих операций со списками.

Рекурсия или цикл: что когда использовать

Всё, что можно сделать с помощью рекурсии, можно сделать и циклом. Так когда же выбирать одно, а когда другое?

Рекурсивный факториал

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

print(factorial(5))  # 120

Итеративный факториал (цикл)

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

print(factorial(5))  # 120

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

Рекурсия раскрывается во всей красе, когда задача по своей природе древовидная или самоподобная. Например, обход структуры папок, разбор вложенных данных (вроде JSON или HTML) и обход деревьев и графов. В таких случаях рекурсия даёт более чистый и короткий код.

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

Рекурсия особенно хороша в задачах, где нужно обойти все ветви древовидной структуры. Вот практический пример: превращение вложенного списка в плоский.

Превращаем вложенный список в плоский с помощью рекурсии

def flatten(lst):

result = []

for item in lst:

if isinstance(item, list):

result.extend(flatten(item)) # Recursion for nested lists

else:

result.append(item)

return result

nested = [1, [2, 3], [4, [5, 6]], 7]

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

Вывод

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

Попробуйте написать это без рекурсии. Вам понадобится вручную вести стек и аккуратно отслеживать, что уже обработано. Рекурсивная версия читается почти как обычная фраза: «Каждый элемент, который сам является списком, разворачиваем, а остальные оставляем как есть».

Частые ошибки в рекурсии

Ошибка 1: нет базового случая

Всегда добавляйте базовый случай

# DON'T run this - it would crash!

# def bad_countdown(n):

# print(n)

# bad_countdown(n - 1) # Never stops!

# The fix: add a base case

def good_countdown(n):

if n <= 0:

return

print(n)

good_countdown(n - 1)

good_countdown(5)

Вывод

Ошибка 2: вызовы не приближаются к базовому случаю

Каждый вызов должен приближаться к базовому случаю

# DON'T run this - n never decreases!

# def bad_factorial(n):

# if n <= 1:

# return 1

# return n * bad_factorial(n) # Oops! Should be n - 1

# The fix: make sure the argument changes

def good_factorial(n):

if n <= 1:

return 1

return n * good_factorial(n - 1) # n - 1 moves toward base case

print(good_factorial(5))

Вывод

Практические упражнения

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

Упражнение 1: предскажите вывод рекурсии

Угадайте вывод

Прочитайте этот код и предскажите, что он выведет. Затем напишите инструкции print(), которые дают точно такой же вывод.

def mystery(n):
    if n <= 0:
        return
    mystery(n - 1)
    print(n)

mystery(3)

Обратите внимание: print(n) стоит после рекурсивного вызова. Хорошо подумайте о порядке.

# Print the exact output of the code above

Упражнение 2: рекурсивная сумма от 1 до N

Напишите код

Напишите рекурсивную функцию sum_to, которая принимает положительное целое число n и возвращает сумму всех чисел от 1 до n.

Например: sum_to(5) должна вернуть 1 + 2 + 3 + 4 + 5 = 15.

Базовый случай: sum_to(1) возвращает 1.

Выведите результаты sum_to(5) и sum_to(10) на отдельных строках.

def sum_to(n):

# Your code here

pass

print(sum_to(5))

print(sum_to(10))

Упражнение 3: исправьте сломанную функцию степени

Исправьте ошибку

Эта рекурсивная функция должна возводить base в степень exp (как base ** exp). Но в ней две ошибки.

Исправьте обе, чтобы вывод был таким:

8
1
81

def power(base, exp):

if exp == 0:

return 0

return base + power(base, exp - 1)

print(power(2, 3))

print(power(5, 0))

print(power(3, 4))

Упражнение 4: числа Фибоначчи с помощью рекурсии

Напишите код

Напишите рекурсивную функцию fibonacci, которая возвращает n-е число Фибоначчи.

Последовательность Фибоначчи начинается так: 0, 1, 1, 2, 3, 5, 8, 13, ...

Правила:

fibonacci(0) возвращает 0

fibonacci(1) возвращает 1

Для n >= 2: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Выведите результаты для n = 0, 1, 5 и 10 на отдельных строках.

def fibonacci(n):

# Your code here

pass

print(fibonacci(0))

print(fibonacci(1))

print(fibonacci(5))

print(fibonacci(10))

Упражнение 5: разверните строку с помощью рекурсии

Напишите код

Напишите рекурсивную функцию reverse, которая принимает строку и возвращает её задом наперёд.

Например: reverse("hello") должна вернуть "olleh".

Подсказка: последний символ плюс развёрнутая версия всего, кроме последнего символа.

Выведите результаты reverse("hello") и reverse("Python") на отдельных строках.

def reverse(s):

# Your code here

pass

print(reverse("hello"))

print(reverse("Python"))

Упражнение 6: подсчёт цифр с помощью рекурсии

Напишите код

Напишите рекурсивную функцию count_digits, которая принимает неотрицательное целое число и возвращает количество его цифр.

Например:

count_digits(0) возвращает 1

count_digits(5) возвращает 1

count_digits(123) возвращает 3

count_digits(99999) возвращает 5

Подсказка: деление на 10 с помощью // убирает последнюю цифру.

Выведите результаты для 0, 5, 123 и 99999 на отдельных строках.

def count_digits(n):

# Your code here

pass

print(count_digits(0))

print(count_digits(5))

print(count_digits(123))

print(count_digits(99999))

Итоги

Вот что вы узнали о рекурсии:

Понятие	Что означает
Рекурсия	Функция, которая вызывает саму себя
Базовый случай	Условие, которое останавливает рекурсию
Рекурсивный случай	Часть, где функция вызывает себя с более простыми входными данными
Стек вызовов	Механизм Python для отслеживания вложенных вызовов функций
Переполнение стека	То, что происходит, когда рекурсия уходит слишком глубоко (нет базового случая)
Рекурсия или цикл	Циклы для простого повторения, рекурсия для древовидных задач

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

Что дальше?

Следующий урок посвящён функциям [map(), filter() и reduce()](/python/python-map-filter-reduce), мощным инструментам функционального программирования в Python. Вы научитесь преобразовывать, фильтровать и объединять коллекции данных в одну строку кода.

Что такое рекурсия?

Базовый случай: когда остановиться

Как работает стек вызовов

Классические примеры рекурсии

Факториал

Сумма элементов списка

Рекурсия или цикл: что когда использовать

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

Частые ошибки в рекурсии

Ошибка 1: нет базового случая

Ошибка 2: вызовы не приближаются к базовому случаю

Практические упражнения

Итоги

Что дальше?

Похожие уроки