Рекурсия — множественные выполнения подпрограммы
Рассмотрим рекурсивную форму вычисления факториала:
Функция f( ) является рекурсивной, так как f(n) вычисляется с помощью f(n - 1),f(n - 1) - с помощью f(n - 2) и так далее до вычисления f(0) = 1.
Последовательность запусков при вызове функции f(3) отобразим графически: f(3) = 3 * f(2) /* приостановка выполнения f(3) */
f(2) = 2 * f(1) /* приостановка выполнения f(2) */
f(1) = 1 * f(0) /* приостановка выполнения f(1) */ f(0) = 1
f(1) = 1 /* возобновление выполнения f(1) */ f(2) = 2 /* возобновление выполнения f(2) */ f(3) = 6 /* возобновление выполнения f (3) */
В ответ на вызов f(3) тело функции выполняется с n = 3: if 3 = 0 then ... else ...
Так как результат сравнения 3 = 0 равен false, начинает вычисляться выражение 3 * f(3 - 1) = 3 * f(2).
Теперь для выполнения умножения требуется значение f(2), поэтому для вычисления f(2) рекурсивно вызывается f( ). Аналогично в ходе запуска для f(2) вызывается f(1). Далее, в ходе запуска f(1) вызывается f(0).
Недостатком рекурсивных подпрограмм для обычных компьютеров является существенное увеличение расхода памяти, ведь под каждый вызов создается дополнительная активация подпрограммы. Хотя, конечно, математикам эта форма очень нравится — она соответствует естественной форме записи вычислений.