Паскаль. Основы программирования


Рекурсия - часть 2


д. до тех пор, пока n не станет равным 1, а значение f получит значение 1 (надо заметить, что при всех предыдущих операциях значение f оставалось равным 0, а точнее говоря, неопределенным).

После этого, начнется обратный процесс, в котором будет выполняться команда: f := f*n. Он будет происходить так:

f := 1*4; f := 4*3; f := 12*2; f := 24*1.

Образно говоря, при первоначальном процессе, значения n от 4 до 1 "запоминаются" в стековую память "Паскаль-машины", а при следующем процессе, значения n "считываются" из стековой памяти “Паскаль-машины”

и умножаются на значения f.

Условно-схематически это можно изобразить так: значения n запоминаются в стек-память "Паскаль-машины":

4

3

4

 

2

3

4

 

1

2

3

4

а затем начинают считываться в обратном порядке, начиная с единицы.

Обязательным элементом в описании всякого рекурсивного процесса является некоторое утверждение, определяющее условие завершения рекурсии; иногда его называют опорным условием рекурсии (или "якорем"). В нашем случае это условие:

if

(n = 0) or (n = 1) then f := 1.

В опорном условии может быть задано какое-то фиксированное значение, заведомо достигаемое в ходе рекурсивного вычисления и позволяющего организовать своевременную остановку процесса; применительно к вычислению факториала им будет равенство 1! = 1. Таким образом, любое рекурсивное определение всегда содержит два элемента: условие завершения и способ выражения одного шага решения посредством другого, более простого шага.

Для четкого понимания происходящих при этом процессов необходимо иметь в виду, что:

а) при каждом вызове процедуры создается новый экземпляр f;

б) все экземпляры f накапливаются во внутреннем стеке “Паскаль-машины” и

в) в любой момент обработке доступен только один, хронологически последний экземпляр переменной f, который

г) по завершению очередного рекурсивного вызова автоматически уничтожается).

Вывод




Начало  Назад  Вперед