Конспект

Рекурсия

Ключевые тезисы

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

Основное содержание

Аналогии и принцип работы

Сказка «Репка»
Задачу (вытащить репку) можно представить как вызов функции. Дед (первый вызов) не может выполнить задачу самостоятельно и вызывает «подпрограмму» — бабку, передавая ей параметр (необходимое усилие). Этот процесс продолжается (бабка → внучка → Жучка → кошка), пока задача не упростится до уровня, который может выполнить «крайний случай» — мышка, не вызывающая никого. Все предыдущие вызовы ожидают результата от следующих, формируя стек вызовов (call stack).

Матрешка
Процесс создания матрешки уровня n:

1. Изготовить верхнюю часть.
2. Изготовить нижнюю часть.
3. Положить внутрь готовую матрешку уровня n-1 (рекурсивный вызов).
   Крайний случай — матрешка уровня 1, которая делается целиком.
   После возврата из рекурсии (обратный ход) происходит сборка: верхняя часть + вложенная матрешка + нижняя часть.

Важные правила рекурсии

1. Обязательны два случая:
   • Рекуррентный случай: способ сведения задачи к более простой подзадаче.
   • Крайний (базовый) случай: условие, при котором задача решается напрямую, без новых вызовов.
2. Без крайнего случая возникает бесконечная рекурсия и переполнение стека вызовов.
3. Подзадача в рекуррентном случае должна быть проще исходной задачи (например, n-1 вместо n).

Примеры рекурсивных алгоритмов

Факториал
Факториал числа n — произведение всех натуральных чисел от 1 до n.

• Крайний случай: fact(0) = 1, fact(1) = 1.
• Рекуррентный случай: fact(n) = n * fact(n-1).

Алгоритм Евклида (НОД)
Нахождение наибольшего общего делителя двух чисел.

• Крайний случай: Если b == 0, то НОД = a.
• Рекуррентный случай: gcd(a, b) = gcd(b, a % b).

Быстрое возведение в степень
Оптимизированный алгоритм за счет уменьшения степени в два раза для четных показателей.

• Крайний случай: pow(a, 0) = 1.
• Рекуррентные случаи:
  • Если степень n нечетная: pow(a, n) = a * pow(a, n-1).
  • Если степень n четная: pow(a, n) = pow(a*a, n//2).

Ханойская башня
Задача переложения пирамиды дисков со стержня на стержень с использованием вспомогательного стержня.

• Крайний случай: Переместить один диск.
• Рекуррентный случай для пирамиды из n дисков:
  1. Переложить пирамиду из n-1 дисков на временный стержень.
  2. Переложить самый большой (n-й) диск на целевой стержень.
  3. Переложить пирамиду из n-1 дисков с временного стержня на целевой.

Рекурсия в графике (Фрактальный прямоугольник)

Идея: нарисовать квадрат, затем внутри него рекурсивно нарисовать уменьшенный подобный квадрат.

• Крайний случай: Глубина рекурсии равна 0 — ничего не рисуем.
• Рекуррентный случай: Нарисовать внешний квадрат, вычислить координаты внутреннего квадрата (уменьшив стороны) и вызвать функцию рисования с глубиной depth-1.

Выводы

• Рекурсия — мощный инструмент для решения задач, которые естественно разбиваются на подобные подзадачи.
• Ключ к написанию рекурсии — четкое определение крайнего случая и рекуррентного соотношения.
• Понимание стека вызовов и пространств имен помогает отлаживать рекурсивные функции.
• Многие классические алгоритмы (факториал, НОД, обход деревьев) имеют элегантные рекурсивные реализации.