В математике рекурсией называется способ описания функций или процессов через самих себя. Например,
В некоторых языках программирования, в том числе и в Паскале, допустимо, чтобы подпрограмма вызывала себя. Такие подпрограммы называются рекурсивными.
Рекурсивная подпрограмма обязательно удовлетворяет двум требованиям:
1) имеет нерекурсивный выход;
2) при каждом рекурсивном обращении задача упрощается, приближаясь к нерекурсивному решению.
При решении некоторых задач можно использовать как рекурсивный, так и итеративный алгоритм. Преимущество рекурсивных подпрограмм заключается в простоте написания, легкости понимания. Обычно это касается задач, связанных с процессами, рекурсивными по своей природе. Но рекурсивные алгоритмы, как правило, менее эффективны из-за затрат времени на организацию стека. При каждом обращении в стеке запоминаются значения всех локальных переменных, параметров и коды возврата. Глубина рекурсии (количество обращений к себе) ограничена объемом памяти стека. При глубокой вложенности рекурсии может произойти переполнение стека.
Пример 5. Опишем рекурсивную и итеративную функцию для вычисления n! :
