<<
>>

Рекурсия — множественные выполнения подпрограммы

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

Рассмотрим рекурсивную форму вычисления факториала:

Функция 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).

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

<< | >>

Еще по теме Рекурсия — множественные выполнения подпрограммы:

  1. 8.3.1. Множественное сознание
  2. Часть III Множественное строение личности
  3. 1. Множественность лиц в обязательстве
  4. 1. Обязательства с множественностью лиц
  5. Множественность Я
  6. НАЗНАЧЕНИЕ НАКАЗАНИЯ ПРИ МНОЖЕСТВЕННОСТИ ПРЕСТУПЛЕНИЙ
  7. Единственность и множественность
  8. Единственность и множественность
  9. способен давать множественные интерпретации.
  10. 2. Исполнение при множественности лиц в обязательстве
  11. § 2. Множественность лиц в обязательстве. Перемена лиц в обязательстве
  12. Статья 530. Срок выполнение обязательства
  13. Статья 846. Сроки выполнения работы
  14. Статья 893. Выполнение работ
  15. 3. Срок выполнения работы.
  16. Статья 538. Встречное выполнение обязательства