Реализация рекурсии

Begin

If n = 0

then F:= 1

else F:= F(n - 1) * n

End;

Вычисление функции F можно представить как цепочку вызовов новых копий этой функции c передачей новых значений аргумента и возвратов значений функции в предыдущую копию.

n-1 n-2 n-3 0

n!

F(n) F(n-1) F(n-2) F(1)

Цепочка вызовов обрывается при передаче нуля в новую копию функции. Дви­жение в прямом направлении (развора­чива­ние рекурсии) сопро­вож­дается только вычислением условия и вызовом.

Значение функции вычисляется при сворачивании це­по­ч­ки вызовов.

Рекур­сивное обращение к проце­дуре (рекурсивный вызов функ­ции) можно представить как

· Построение в памяти компьютера новой копии этой процедуры;

· Передачу управления в эту новую копию (с новыми значениями параметров);

· Обработку (возможно – рекурсивную) данных в этой копии;

· Возврат в предыдущую копию (с прежними значе­ни­ями параметров)

Дата добавления: 2014-01-06