✧ Функция зовёт себя ✧

🚀 Запускаем

За три секунды до баннера идёт отсчёт. Вместо цикла запусти вот это:

def countdown(n):
    if n == 0:
        print("Молитва открыта!")
        return
    print(n)
    countdown(n - 1)

countdown(3)
3
2
1
Молитва открыта!

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

📜 Теория: рекурсия

Из чего состоит рекурсия

У любой правильной рекурсивной функции две части:

  • базовый случай — когда ответ очевиден и функция не вызывает себя (n == 0 в примере);
  • шаг рекурсии — вызов себя с задачей поменьше, которая приближает нас к базовому случаю (n - 1).

Без базового случая функция вызывала бы себя бесконечно, и Python остановил бы её сам:

def forever(n):
    return forever(n + 1)

forever(0)
RecursionError: maximum recursion depth exceeded

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

Рекурсия, которая возвращает значение

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

print(fact(5))     # → 120   5 · 4 · 3 · 2 · 1

Как это читать: «факториал n — это n, умноженное на факториал n - 1, а факториал единицы равен единице». Каждый вызов ждёт ответа следующего и потом умножает. Попробуй мысленно разложить fact(3): 3 * fact(2) → 3 * (2 * fact(1)) → 3 * (2 * 1) → 6.

def to_binary(n):
    if n < 2:
        return str(n)
    return to_binary(n // 2) + str(n % 2)

print(to_binary(10))    # → 1010

Идея та же: запись числа — это запись его половины плюс последняя цифра. Здесь порядок важен: цифра дописывается справа после возврата из рекурсии.

Где рекурсия по-настоящему нужна

def total(items):
    result = 0
    for item in items:
        if isinstance(item, list):      # вложенный список — сумма его самого
            result += total(item)
        else:
            result += item
    return result

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

Когда глубина вложенности заранее не известна (списки в списках, папки в папках, деревья), рекурсия самая естественная: «обработай то, что видишь, а вложенное отдай той же функции». С такими данными мы встретимся в разделе про файлы и в алгоритмах. Заметь, что isinstance(item, list) проверяет, является ли значение списком.

Когда рекурсия плохая

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Числа Фибоначчи, записанные так, красивы, но на fib(35) программа заметно задумается: одни и те же значения считаются снова и снова. Правило: если задачу так же легко решить циклом и вложенность не растёт — выбирай цикл, он быстрее и не упирается в предел глубины. Рекурсия нужна там, где данные сами устроены как «матрёшка».

🧪 Попробуй сам

★★★

🎯 Задача: Отсчёт до баннера

10 очков

За n секунд до начала баннера идёт отсчёт: выводятся числа от n до 1 по одному в строке, а после них — Молитва открыта!. Если n равно 0, выводится только последняя фраза.

Напиши рекурсивную функцию countdown(n) (без циклов) и вызови её для числа, прочитанного из ввода.

Пример. Ввод 3, вывод:

3
2
1
Молитва открыта!

Заготовка (кнопка у блока отправит её в песочницу):

# 1. Функция countdown(n): базовый случай — когда считать нечего; иначе выведи число и вызови себя с n - 1

# 2. Прочитай n и вызови функцию
★★★

🎯 Задача: Шифр хиличурлов

25 очков

Хиличурлы передают числа двоичным кодом: нули и единицы. Напиши рекурсивную функцию to_binary(n), которая возвращает двоичную запись неотрицательного числа в виде строки (для 0 — 0, для 5 — 101). Идея: двоичная запись числа — это запись числа n // 2, к которой справа дописана цифра n % 2.

Программа читает число n (от 0 до 255) и выводит две строки: код и количество единиц в нём.

Пример. Ввод 10, вывод:

Двоичный код: 1010
Единиц: 2

Заготовка (кнопка у блока отправит её в песочницу):

# 1. Функция to_binary(n): базовый случай — маленькое число записывается само; иначе склей запись половины и последнюю цифру

# 2. Прочитай число, получи код и посчитай единицы

✅ Что мы узнали

Рекурсия — функция, вызывающая себя. Ей нужны базовый случай (когда пора остановиться) и шаг, приближающий к нему; без базового случая получим RecursionError. Рекурсивные функции могут и печатать, и возвращать значения; порядок «действие до вызова» и «после вызова» меняет результат. Для вложенных данных рекурсия естественна, для простых повторов лучше цикл.

С функциями разобрались. Дальше — как программа справляется с ошибками и работает с файлами.

⟵ Функция как значение Ловим ошибки ⟶