Рекурсия (ЕГЭ-ОГЭ)

В программировании под рекурсией понимают вызов функции (процедуры) самой себя — напрямую (простая рекурсия) или через другие функции (сложная или косвенная рекурсия). Например, функция ${\displaystyle A}$ вызывает функцию ${\displaystyle B}$, а та, в свою очередь, обращается к функции ${\displaystyle A}$. Число вложенных вызовов функции или процедуры называют глубиной рекурсии. Применение рекурсии позволяет описывать повторяющиеся или потенциально неограниченные вычисления без явного дублирования кода и без использования циклов.

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

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

Теоретически любую рекурсивную функцию можно заменить на комбинацию цикла и явного управления стеком, однако на практике это малоэффективно, так как требует ручного сохранения контекста и увеличивает расход памяти. Исключение составляют ситуации, когда рекурсия не поддерживается языком программирования.

Для обоснования корректности рекурсивной функции необходимо доказать:

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

Под рекурсивным определением данных понимают ситуацию, когда структура данных (запись, объект) содержит вложенный объект, структурно аналогичный самому себе или, что встречается чаще, ссылку на такой же объект. Преимущество такого способа описания заключается в том, что одно конечное определение способно описать потенциально бесконечную структуру данных. Подобные конструкции применяются при представлении списков и графов.

Для обработки рекурсивных структур данных обычно применяются рекурсивные методы. В последнее время получила распространение концепция «ленивых вычислений», при которой значения вычисляются только по мере необходимости. Некоторые языки программирования (Python) поддерживают работу с потенциально бесконечными рекурсивными последовательностями без явных ограничений на создание объектов.

Ниже приведена рекурсивная функция на Pascal, вычисляющая факториал натурального числа. Факториал числа ${\displaystyle n}$, обозначаемый ${\displaystyle n!}$, представляет собой произведение натуральных чисел от 1 до ${\displaystyle n}$: 1⋅2⋅…⋅(n−1)⋅n.

function Factorial(n: integer): longint;

begin

if n = 1 then Factorial:= 1

else Factorial:= n*Factorial(n-1);

end;