Рекурсивные подпрограммы

В математике рекурсией называется способ описания функций или процессов через самих себя. Например,

В некоторых языках программирования, в том числе и в Паскале, допустимо, чтобы подпрограмма вызывала себя. Такие подпрограммы называются рекурсивными.

Рекурсивная подпрограмма обязательно удовлетворяет двум требованиям:

1) имеет нерекурсивный выход;

2) при каждом рекурсивном обращении задача упрощается, приближаясь к нерекурсивному решению.

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

Пример 5. Опишем рекурсивную и итеративную функцию для вычисления n!: