2015-02-24
348
Процесс, состояние которого на текущем шаге зависит от состояния этого же процесса на предыдущих шагах, называется многошаговым итерационным процессом.
Примерами итерационных процессов являются:
- вычисление суммы: S0=0, S n= Sn-1 + un, n=1,2,…;
- вычисление произведения: P0 = 1, Pn = Pn-1 * mn,, n=1,2,…;
- вычисление факториала: 0!=1, k! = (k-1)! * k;
- вычисление чисел Фибоначчи: F1=1, F2=2, Fn = Fn-1 + Fn-2.
Рекурсия определяется как способ описания объектов, данных процессов или функций через самих себя. Процесс на очередном шаге определяется через тот же самый процесс напредыдущемшаге. Чтобы перейти к рекуррентному определению в программе, необходимо для описания процесса определить предикат, который обращался бы к самому себе, т.е. к описанию того же процесса, при других значениях аргументов. При этом допускается, что уже имеется процесс, который правильно выполняется и позволяет получить состояние на предшествующем шаге.
Пример. Вычислить факториал F=n!
Predicates
Fact(integer,integer)
