Пример подсчета факториала

1, n=0

N!=

N*(n-1)!, >0

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

Var

M:longint;

Function factorial (n:word): longint;

Begin

If n=0 then factorial:=1

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

End;

Begin

M:=factorial (4);

End.

Работа данной функции: при вызове функции Factorial(4) в стек поступает копия параметра n elau n=0, то вызывает эта же функция с параметром n-1

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

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

Лекция №6

Подпрограммы. Внешние подпрограммы. Подпрограммы в качестве параметров подпрограмм. Примеры.