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

Рекурсивный алгоритм – это способ решения задач, в котором функция (или процедура) вызывает саму себя на «меньших» подзадачах до достижения базового случая. Рекурсия естественна для обработки структур с индуктивной природой (строки, списки, деревья, графы, диапазоны чисел), а также для стратегий «разделяй и властвуй» и поиска с откатом. В тексте формализованы понятия рекурсии, разобраны виды и правила корректного проектирования (базовый случай, монотонная мера, глубина стека, детерминированность, идемпотентность эффектов), показаны приёмы анализа сложности через рекуррентные соотношения и дерево рекурсии. Связь с ЕГЭ проявляется в умении трассировать вызовы, вычислять значения рекурсивно заданных функций, оценивать число операций и глубину стека, преобразовывать рекурсивные решения в итеративные и обратно. Завершает материал практикум из пяти упражнений формата «условие → критерии → подсказки», совместимых с экзаменационными компетенциями.

Формальная модель рекурсии и вычислительная семантика

Определение. Рекурсивный алгоритм задаётся парой:

• Базовый случай (основание индукции): конечное число входов, для которых ответ определён без дальнейших вызовов.
• Рекурсивный шаг: редукция задачи размера n к одной или нескольким подзадачам меньшего размера n' < n с последующей композицией их результатов.

Вычислительная модель. Каждому вызову соответствует активационная запись (кадр стека), содержащая параметры, локальные переменные, адрес возврата, частичные результаты. В момент вызова создаётся новый кадр; при возврате – кадр снимается. Процесс завершается, когда вычислен базовый случай для всех ветвей вызовов.

Корректность завершения обеспечивается существованием монотонной меры μ на входах (например, длина списка, глубина дерева, разность границ r−l), которая строго убывает на каждом рекурсивном шаге и ограничена снизу.

Классификация рекурсии

1. По структуре данных
   

   • Числовая (на натуральных): f(n) → f(n−1), f(n−2) и т. п.

   • Структурная (на списках/деревьях): f(cons(x, xs)) → g(x, f(xs)), f(node) → combine(f(left), f(right)).

2. По числу подзадач
   

   • Линейная: одна подзадача (напр., хвостовая, бинарный поиск).

   • Ветвящаяся (разветвлённая): несколько подзадач (быстрая сортировка, обход дерева, разбиения множества).

3. По положению рекурсивного вызова
   

   • Хвостовая (tail): вызов – последняя операция; теоретически оптимизируема до итерации.

   • Нехвостовая: после возврата требуется дополнительная работа (например, 1 + f(n−1)).

4. По схеме вызовов
   

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

   • Косвенная: f вызывает g, а g – f.

5. По целям
   

   • Разделяй-и-властвуй (divide & conquer): делим на равные/неравные части, комбинируем (сортировки, умножение Карацубы).

   • Поиск с откатом (backtracking): перебор с проверкой ограничений (лабиринты, расстановка ферзей).

   • ДП через мемоизацию: рекурсивная формула + кэш значений.

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

1. Сначала базовый случай
   

   • Чётко зафиксируйте множество тривиальных входов; проверьте их до рекурсивных вызовов.

   • Базовые случаи должны покрывать крайние границы (пустая строка, пустой список, один элемент, ноль, отрицательные входы – если допустимы).

2. Строго убывающая мера
   

   • Для каждого шага покажите, какая метрика уменьшается: длина, высота, диапазон, число узлов.

   • В косвенной рекурсии убедитесь, что мера убывает вдоль цикла f→g→f.

3. Ограничение глубины стека
   

   • Оцените depth(n) – максимальную глубину вызовов. Типично: линейная O(n) (линейная рекурсия), логарифмическая O(log n) (бинарный поиск, деление пополам), до O(height) на дереве.

4. Детерминизм и реентерабельность
   

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

5. Экономия вычислений
   

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

6. Хвостовая нормальная форма
   

   • При возможности перепишите в хвостовую форму для эквивалентности итерации. В школьных средах оптимизация хвостовой рекурсии чаще не включена – учитывайте риск переполнения стека.

7. Чёткая спецификация
   

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

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

Рекуррентные соотношения описывают время T(n) и/или память:

• Линейная: T(n) = T(n−1) + c → T(n) = Θ(n).
• Дихотомическая: T(n) = T(n/2) + c → Θ(log n).
• Разветвлённая: T(n) = a·T(n/b) + f(n); при регулярных делениях удобно применять «метод мастер-теоремы» (в школьной постановке – через дерево рекурсии и суммирование уровней).
• Полный перебор: T(n) = 2·T(n−1) + c → Θ(2^n).

Память стека пропорциональна максимальной глубине невозвращённых вызовов: S(n) = O(depth(n)). Для «разделяй-и-властвуй» на две половины глубина O(log n); для линейных – O(n).

Типовые шаблоны и примеры (псевдокод)

Хвостовая рекурсия (сумма массива)

sum(A[0..n-1], acc=0):

  if n == 0: return acc

  return sum(A[0..n-2], acc + A[n-1])

Сложность Θ(n), глубина Θ(n); легко превращается в цикл.

Бинарный поиск (логарифмическая глубина)

binsearch(A, x, l, r):  // A отсортирован, ищем x в [l..r)

  if l >= r: return -1

  m = floor((l + r)/2)

  if A[m] == x: return m

  if A[m] > x:  return binsearch(A, x, l, m)

  else:         return binsearch(A, x, m+1, r)

T(n)=T(n/2)+O(1) → Θ(log n); стек Θ(log n).

DFS по дереву (структурная рекурсия)

height(node):

  if node == null: return 0

  return 1 + max(height(node.left), height(node.right))

Глубина = высоте дерева.

Фибоначчи: наивно vs мемоизация

fib(n):

  if n <= 1: return n

  return fib(n-1) + fib(n-2)  // экспоненциально

fibM(n, memo):

  if n in memo: return memo[n]

  if n <= 1: memo[n]=n

  else: memo[n]=fibM(n-1,memo)+fibM(n-2,memo)

  return memo[n]              // линейно по n

Разделяй-и-властвуй (подсчёт инверсий слиянием)

Идея: при слиянии отсортированных половин считать пары (i,j) с A[i] > A[j]. Сложность Θ(n log n) при глубине Θ(log n).

Связь с подготовкой к ЕГЭ по информатике

На ЕГЭ встречаются задачи, где нужно:

• Трассировать рекурсивную программу: определить порядок вывода, число вызовов, конечный результат.
• Вычислить значение рекурсивной функции для заданного n либо для набора параметров (в том числе с ветвлением условий).
• Оценить сложность (сколько раз печатается число/выполняется операция), посчитать глубину стека.
• Преобразовать рекурсивный алгоритм в итеративный (или наоборот), сохранив логику.
• Распознать переполнение стека и корректно ввести базовые случаи и порядок проверок.
• Использовать рекурсивные обходы в задачах на деревья/графы, генерацию последовательностей и комбинаторных объектов (перестановки, пути на решётке) – часто с применением мемоизации.

Практика по рекурсии тренирует алгоритмическое мышление, аккуратность в определении предикатов выхода, понимание структуры вычислений – это прямо повышает результативность в заданиях повышенной сложности.

Типичные ошибки и способы избежать их

• Отсутствует или неверен базовый случай. Решение: выделить минимальные входы и убедиться, что все рекурсивные ветви их достигают.
• Мера не убывает. Решение: доказать убывание явно; для косвенной рекурсии – на цикл взаимных вызовов.
• Побочные эффекты в локальных переменных общие для ветвей. Решение: избегать разделяемого состояния, использовать чистые функции.
• Экспоненциальная избыточность вычислений. Решение: кэширование результатов (мемоизация) или динамическое программирование.
• Переполнение стека. Решение: хвостовая форма/итерация, ограничение глубины (например, ограничить n в задачах ЕГЭ), разбить на цикл.
• Проверка базового случая после рекурсивного вызова. Всегда проверяйте до.

Практикум: 5 упражнений (ЕГЭ-ориентированный формат)

Упражнение 1. Трассировка и порядок вывода
Условие. Рассмотрим функцию:

F(n):

  if n <= 0: print «X»; return

  print n

  F(n - 2)

  print n

Для n = 5 укажите последовательность печати на экране и общее число вызовов F.
Критерии. Корректное следование порядку вызовов (до и после рекурсии), учёт базового случая, подсчёт вызовов (включая базовые).
Подсказки. Постройте дерево вызовов по уровням n=5→3→1→-1.

Упражнение 2. Число операций и глубина стека
Условие. Пусть

G(n):

  if n == 1: return 1

  return 1 + G(n // 2)

1. Сколько раз выполняется операция «прибавить 1» для n = 1000?

2. Какова асимптотическая глубина стека и время работы?
   Критерии. Узнавание логарифмической рекурсии T(n)=T(n/2)+O(1), оценка Θ(log n).
   Подсказки. Подсчитайте число делений пополам до единицы: ⌊log2 n⌋.

Упражнение 3. Рекурсивная функция с мемоизацией
Условие. Определите число способов набрать сумму S из монет номиналов 1, 3, 4 (монет бесконечно, порядок не важен). Напишите рекурсивное определение ways(S) и предложите схему мемоизации.
Критерии. Правильная постановка рекуррентного соотношения с учётом «порядок не важен» (фиксированный набор номиналов и их индекса), корректные базовые случаи (S=0 → 1 способ, S<0 → 0).
Подсказки. Используйте индекс по номиналам: ways(i, S) – считаем способами с монетами {1..i}; мемоизируйте по паре (i, S).

Упражнение 4. Рекурсивная проверка палиндрома (строка)
Условие. Задано слово s. Определите рекурсивный алгоритм isPal(s) без циклов: сравнивайте крайние символы и рекурсируйте на подстроке. Оцените время и память на стек.
Критерии. Базовый случай для строк длины 0 и 1, корректное уменьшение задачи (обрезание краёв), оценка Θ(n) по времени и Θ(n) по стеку (при наивной реализации).
Подсказки. Хвостовую форму получить сложно из-за сравнения пары символов и сдвига границ, но можно передавать индексы l, r.

Упражнение 5. Разделяй-и-властвуй: количество инверсий
Условие. Требуется посчитать число инверсий в массиве A[0..n-1] (пар (i,j), где i<j и A[i]>A[j]), используя модифицированную рекурсивную сортировку слиянием. Опишите рекурсивную схему и оцените сложность.
Критерии. Верная декомпозиция: делим массив пополам, считаем инверсии в левой и правой частях, плюс «сквозные» при слиянии; время Θ(n log n), стек Θ(log n).
Подсказки. На этапе слияния, когда left[i] > right[j], добавляется left_remaining = len(left) - i.

Заключение

Рекурсивные алгоритмы – фундаментальная техника, позволяющая естественно выразить решения на индуктивных структурах и задачах, где доминируют деление проблемы и композиция частичных результатов. Формальная дисциплина – чёткий базовый случай, строго убывающая мера, корректная оценка глубины стека и времени, контроль побочных эффектов и экономия вычислений за счёт мемоизации – делает рекурсию практичным инструментом для олимпиадной и экзаменационной практики. Для ЕГЭ ключевые компетенции – трассировка, вычисление значений, оценка сложности и умение переписывать рекурсию в итерацию – непосредственно тренируются на предложенных упражнениях и типовых шаблонах (бинарный поиск, обход дерева, палиндром, «разделяй-и-властвуй»). Освоив эти принципы, выпускник уверенно решает задачи повышенной сложности, демонстрируя глубокое понимание алгоритмических идей и строгую культуру доказательства корректности.