Основы программирования

Рекурсия

**Загадка:** Как вычислить факториал без цикла? Подсказка: 5! = 5 × 4!, а 4! = 4 × 3!, и так далее... Ответ - рекурсия: функция, которая вызывает сама себя.

Рекурсия - это как матрёшка: открываешь одну - внутри другая. Открываешь ту - ещё одна. И так до самой маленькой. Потом собираешь обратно.

Цели урока

  • Понять концепцию рекурсии
  • Научиться определять базовый случай
  • Освоить рекурсивные алгоритмы
  • Понять когда рекурсия лучше цикла (и наоборот)

Предварительные знания

  • Функции (урок 8)
  • Условные операторы (урок 6)

Файловая система - рекурсивная структура: папка содержит папки, которые содержат папки... Обход дерева, парсинг JSON, сортировка - везде рекурсия.

  • **Файловый менеджер**: обход всех папок и файлов
  • **JSON/XML**: парсинг вложенных структур
  • **Алгоритмы**: быстрая сортировка, бинарный поиск
  • **Игры**: генерация фракталов, лабиринтов

От лямбда-исчисления Чёрча до Quicksort и отсутствия TCO в Python

Рекурсия как формальная концепция родилась в 1936 году. Алонзо Чёрч опубликовал лямбда-исчисление, где функция могла применяться к самой себе. В том же 1936 Чёрч и Хаскелл Карри (Карри начал работу ещё в 1929) описали комбинатор неподвижной точки Y, который позволяет анонимной функции вызвать саму себя без имени. Это математическая основа всей рекурсии в функциональных языках. В 1958 году Джон Маккарти создал Lisp в MIT и сделал рекурсию основным способом вычислений: сам интерпретатор eval определялся рекурсивно через apply. В 1959 году Тони Хоар изобрёл Quicksort, и алгоритм был естественно рекурсивным: сортируем меньшие отдельно, большие отдельно, склеиваем. С 1976-1977 Гай Стил и его коллеги в серии Lambda Papers (Scheme в MIT) показали, что хвостовые вызовы можно превращать в простые goto без роста стека. С тех пор tail call optimization (TCO) стала стандартом в Scheme, Standard ML, Erlang, OCaml, Haskell. Питон пошёл другим путём. В апреле 2009 года Гвидо ван Россум опубликовал заметку Tail Recursion Elimination в блоге Neopythonic и отказался добавлять TCO в CPython. Аргументы: чистый стек важен для отладки, рекурсия в Python не идиоматична (есть for и while), и оптимизация хвостовых вызовов скроет ошибки рекурсии. Поэтому в Python sys.getrecursionlimit() по умолчанию 1000 и глубокая рекурсия всё ещё падает с RecursionError.

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

**Рекурсия** - это когда функция вызывает сама себя. Звучит странно, но это естественный приём для задач, которые можно разбить на подзадачи.

Простейший пример

Обратный отсчёт

```python def countdown(n): if n <= 0: # Базовый случай - когда остановиться print("Пуск!") else: print(n) countdown(n - 1) # Рекурсивный вызов countdown(5) # 5 # 4 # 3 # 2 # 1 # Пуск! ```

**Два ключевых элемента рекурсии:** 1. **Базовый случай** - условие выхода (когда остановиться) 2. **Рекурсивный случай** - вызов самой себя с изменённым параметром

Как это работает?

Стек вызовов

``` countdown(3) вызывает: print(3) countdown(2) вызывает: print(2) countdown(1) вызывает: print(1) countdown(0) вызывает: print("Пуск!") ← Базовый случай, выход возврат возврат возврат возврат ``` Каждый вызов "ждёт" завершения внутреннего вызова.

Что произойдёт, если забыть базовый случай в рекурсии?

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

**Базовый случай** - это условие, при котором рекурсия останавливается. Без него - бесконечный цикл и ошибка.

Правильный базовый случай

Сумма чисел от 1 до n

```python def sum_to(n): # Базовый случай if n == 1: return 1 # Рекурсивный случай return n + sum_to(n - 1) print(sum_to(5)) # 5 + 4 + 3 + 2 + 1 = 15 # Как это разворачивается: # sum_to(5) = 5 + sum_to(4) # = 5 + 4 + sum_to(3) # = 5 + 4 + 3 + sum_to(2) # = 5 + 4 + 3 + 2 + sum_to(1) # = 5 + 4 + 3 + 2 + 1 = 15 ```

**Выбор базового случая важен!** Убедись, что: 1. Рекурсия ВСЕГДА достигает базового случая 2. Каждый вызов приближает к базовому случаю 3. Базовый случай обрабатывает все "крайние" ситуации

Несколько базовых случаев

Иногда нужно больше одного

```python def fibonacci(n): # Два базовых случая! if n == 0: return 0 if n == 1: return 1 # Рекурсивный случай return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(7)) # 13 # 0, 1, 1, 2, 3, 5, 8, 13... ```

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

Классика: факториал

**Факториал** n! = n × (n-1) × (n-2) × ... × 1. Это идеальный пример для рекурсии: 5! = 5 × 4!

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

Математическое определение = код

```python def factorial(n): # Базовый случай: 0! = 1, 1! = 1 if n <= 1: return 1 # Рекурсивный случай: n! = n × (n-1)! return n * factorial(n - 1) print(factorial(5)) # 120 # Раскрутка: # factorial(5) = 5 * factorial(4) # = 5 * 4 * factorial(3) # = 5 * 4 * 3 * factorial(2) # = 5 * 4 * 3 * 2 * factorial(1) # = 5 * 4 * 3 * 2 * 1 = 120 ```

Сколько рекурсивных вызовов сделает factorial(4)?

Рекурсия vs Итерация

Любую рекурсию можно переписать как цикл (и наоборот). Но иногда одно элегантнее другого.

Сравнение подходов

Факториал двумя способами

```python # Рекурсия - элегантно, но затратно по памяти def factorial_rec(n): if n <= 1: return 1 return n * factorial_rec(n - 1) # Итерация - быстрее, но менее выразительно def factorial_iter(n): result = 1 for i in range(2, n + 1): result *= i return result # Результат одинаковый print(factorial_rec(5)) # 120 print(factorial_iter(5)) # 120 ```

АспектРекурсияИтерация
ЧитаемостьЧасто элегантнееМожет быть сложнее
ПамятьРасходует стекЭкономнее
СкоростьМедленнее (накладные расходы)Быстрее
Деревья, графыИдеально подходитНужен явный стек
Простые циклыИзбыточноЛучший выбор

**Когда использовать рекурсию:** - Древовидные структуры (файлы, JSON, DOM) - Задачи типа "разделяй и властвуй" - Когда рекурсивное определение естественно (факториал, Фибоначчи)

Для какой задачи рекурсия НАИБОЛЕЕ подходит?

Ловушки рекурсии

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

Проблема 1: Переполнение стека

RecursionError

```python # Слишком глубокая рекурсия def deep(n): if n == 0: return 0 return 1 + deep(n - 1) # deep(10000) # RecursionError: maximum recursion depth exceeded # Решение: использовать итерацию для больших n import sys print(sys.getrecursionlimit()) # 1000 (по умолчанию) ```

Проблема 2: Повторные вычисления

Фибоначчи - плохой пример

```python # Наивная рекурсия - ОЧЕНЬ медленно! def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) # fib(40) - будет считать минуты! # Потому что fib(38) вычисляется дважды, fib(37) - трижды и т.д. # Решение: мемоизация (кэширование) from functools import lru_cache @lru_cache(maxsize=None) def fib_fast(n): if n <= 1: return n return fib_fast(n - 1) + fib_fast(n - 2) print(fib_fast(100)) # Мгновенно! ```

**@lru_cache** - декоратор, который запоминает результаты вызовов. Если функция вызвана с теми же аргументами - возвращает закэшированный результат.

Рекурсия всегда лучше/хуже циклов

Рекурсия - инструмент. Используй её, когда структура задачи рекурсивна

Для линейных задач (сумма массива) цикл проще и быстрее. Для древовидных структур (обход папок, парсинг JSON) рекурсия естественнее и читаемее.

Почему наивный рекурсивный Фибоначчи медленный?

Связь с другими темами

Рекурсия опирается на функции и стек вызовов, открывает путь к scope, структурам и алгоритмам:

  • Функции — Рекурсия это функция, которая вызывает саму себя
  • Область видимости — Каждый рекурсивный вызов создаёт свой scope в стеке
  • Массивы и списки — Рекурсия естественна для разбиения списка на голову и хвост
  • Паттерны проектирования — Composite, Visitor, divide-and-conquer строятся на рекурсии

Итог

  • Рекурсия как формализм пришла из лямбда-исчисления Чёрча 1936 года, комбинатор Y описан Карри (1929) и Чёрчем (1936)
  • Lisp Маккарти (MIT, 1958) сделал рекурсию основным способом вычислений, eval определён рекурсивно через apply
  • Quicksort (Хоар, 1959) и обходы деревьев натурально рекурсивны, для них рекурсия короче и читаемее цикла
  • Tail call optimization стандарт в Scheme и ML с конца 1970-х (Lambda Papers Стила), но Гвидо в апреле 2009 публично отказался добавлять TCO в CPython
  • Дефолтный sys.getrecursionlimit() в Python это 1000, глубокая рекурсия падает с RecursionError, для линейных задач выбирают цикл

Связанные уроки

  • prog-08-functions — Рекурсия это функция которая вызывает себя
  • prog-07-loops — Циклы и рекурсия оба выражают повторение
  • prog-10-scope — Каждый рекурсивный вызов получает свою локальную область
  • alg-19-divide-conquer — Разделяй и властвуй делит задачи рекурсивно
  • ds-09-trees-intro — Деревья естественно обходятся рекурсией
  • alg-01-big-o
Рекурсия

0

1

Войти