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

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

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

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

База и шаг рекурсии

Любая правильная рекурсивная функция состоит из двух обязательных частей:

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

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

Пример: факториал

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

факт(n) = 1, если n = 0 или n = 1 (база)
факт(n) = n · факт(n - 1), если n > 1 (шаг)

На школьном алгоритмическом языке:

алг цел факт(цел n)
нач
  если n <= 1 то
    знач := 1
  иначе
    знач := n * факт(n - 1)
  все
кон

Стек вызовов

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

Числа Фибоначчи

Ещё один классический пример — последовательность Фибоначчи, где каждое число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13... Здесь рекурсия особенно наглядна: фиб(n) = фиб(n-1) + фиб(n-2), а базой служат первые два числа, равные единице.

Частые ошибки. Не забывайте базу — иначе бесконечная рекурсия. Следите, чтобы каждый шаг приближался к базе (аргумент уменьшался). Помните, что слишком глубокая рекурсия может переполнить стек, а наивный рекурсивный Фибоначчи очень медленный из-за повторных вычислений.

Кратко о главном

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