Обсудить задачу
Термин · Р

Рекурсия

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

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

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

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

Классический пример — факториал: 5! = 5 · 4!, а 1! = 1.

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

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

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

import os

def folder_size(path):
    total = 0
    for entry in os.scandir(path):
        if entry.is_dir(follow_symlinks=False):
            total += folder_size(entry.path)
        else:
            total += entry.stat(follow_symlinks=False).st_size
    return total

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

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

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

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

Любую рекурсию можно переписать циклом, и наоборот. Рекурсия часто короче и понятнее для вложенных структур, цикл — экономнее по памяти. Некоторые языки (Scheme, а в функциональном стиле и другие) оптимизируют хвостовую рекурсию, когда рекурсивный вызов стоит последним, и тогда стек не растет. Python и Java такой оптимизации не делают, поэтому для глубокой вложенности в них лучше цикл с явным стеком. В функциональном программировании рекурсия — основной способ повторения, а в структурах данных вроде деревьев — естественный способ обхода.