Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

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

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

    Оглавление:

    Ты стоишь в длинной очереди в столовой и хочешь узнать, какой ты по счету. Начала очереди не видно, поэтому ты спрашиваешь соседа впереди. Он тоже не знает и спрашивает своего соседа. Так вопрос доходит до первого человека: он стоит у кассы и точно знает, что он первый. Дальше ответ идет обратно — каждый прибавляет единицу к номеру соседа, пока цепочка не дойдет до тебя.

    Каждый в очереди узнает свой номер через такой же вопрос соседу. Это и есть рекурсия: функция вызывает сама себя для задачи попроще.

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

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

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

    Простейший пример — обратный отсчет:

    def countdown(n):
        if n == 0:          # базовый случай
            print("Старт!")
            return
        print(n)
        countdown(n - 1)    # шаг рекурсии: задача на единицу меньше
    
    
    countdown(3)
    # 3
    # 2
    # 1
    # Старт!
    

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

    Функция, которая возвращает результат

    Рекурсия особенно удобна, когда ответ для большой задачи легко собрать из ответа для маленькой. Посчитаем сумму цифр числа. Сумма цифр 472 — это последняя цифра 2 плюс сумма цифр числа 47. А у однозначного числа сумма цифр равна ему самому — это базовый случай.

    def digit_sum(n):
        if n < 10:                          # базовый случай: одна цифра
            return n
        return n % 10 + digit_sum(n // 10)  # последняя цифра + сумма остальных
    
    
    print(digit_sum(472))   # 13
    print(digit_sum(2026))  # 10
    

    Здесь n % 10 — последняя цифра числа, а n // 10 — число без последней цифры: 472 // 10 равно 47.

    Стек вызовов

    Что происходит при вызове digit_sum(472)? Сразу вернуть ответ функция не может: ей нужен результат digit_sum(47). Поэтому она замирает и ждет, а Python запускает новый вызов. Тот тоже ждет следующего:

    Вызов Что делает Возвращает
    digit_sum(472) ждет digit_sum(47), потом прибавит 2 $2 + 11 = 13$
    digit_sum(47) ждет digit_sum(4), потом прибавит 7 $7 + 4 = 11$
    digit_sum(4) базовый случай, отвечает сразу $4$

    Таблицу читай сверху вниз — так вызовы «спускаются», а потом снизу вверх — так возвращаются ответы.

    Незавершенные вызовы Python хранит в стеке вызовов. Стек устроен как стопка тарелок: новый вызов кладется сверху, а снимается первым тот, что положили последним. Для каждого вызова Python помнит, где тот остановился, и хранит его собственную копию n, поэтому вызовы друг другу не мешают.

    Ограничение глубины

    Каждый ожидающий вызов занимает память, поэтому Python ограничивает глубину рекурсии — по умолчанию около 1000 вложенных вызовов. Вот что будет, если забыть базовый случай:

    import sys
    
    print(sys.getrecursionlimit())  # 1000
    
    
    def countdown(n):
        print(n)
        countdown(n - 1)    # базового случая нет
    
    
    countdown(3)
    # 3
    # 2
    # 1
    # 0
    # ... и так почти тысячу строк, а затем:
    # RecursionError: maximum recursion depth exceeded...
    

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

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

    Любую рекурсию можно заменить циклом, и часто цикл даже проще. Зачем тогда рекурсия?

    Она выручает, когда задача сама устроена «вложенно»: папки внутри папок, разделы книги с подразделами. Посчитаем сумму чисел в списке, внутри которого могут быть другие списки:

    def nested_sum(items):
        total = 0
        for x in items:
            if isinstance(x, list):     # внутри снова список - та же задача
                total += nested_sum(x)
            else:                       # базовый случай: просто число
                total += x
        return total
    
    
    print(nested_sum([1, [2, 3], [4, [5, 6]]]))  # 21
    

    isinstance(x, list) проверяет, является ли x списком. Сколько уровней вложенности встретится, заранее неизвестно, поэтому простым циклом тут не обойтись. На рекурсии построены и многие быстрые алгоритмы: сортировка слиянием, быстрая сортировка, обход деревьев.

    Частые ошибки

    Частая ошибка: Забытый return перед рекурсивным вызовом. Если в digit_sum написать просто n % 10 + digit_sum(n // 10), функция посчитает сумму и выбросит ее, вернув None. Уровнем выше Python попробует сложить число с None и упадет с TypeError.

    • Нет базового случая — функция вызывает себя, пока не упрется в предел глубины, и падает с RecursionError.
    • Шаг не приближает к базовому случаю. Вызов countdown(-1) с проверкой if n == 0 до нуля не дойдет: -1, -2, -3 и дальше вниз. Надежнее проверять if n <= 0.

    Проверь себя

    1.

    Что произойдет, если у рекурсивной функции нет базового случая?

    2.

    Что вернет вызов digit_sum(9081) для функции из статьи?

    3.

    Соедини понятие и его смысл.

    Базовый случай

    Здесь Python хранит вызовы, которые ждут ответа

    Шаг рекурсии

    Ошибка при превышении глубины рекурсии

    Стек вызовов

    Вызов функции для задачи поменьше

    RecursionError

    Ответ известен сразу, без нового вызова

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами