GOAL: fib(4,X)

Восходящая рекурсия

Моделирование процесса начинается сначала, с момента k=0. Номер шага постоянно возрастает: k= k+1. В качестве правила остановки выбирается момент достижения условий окончания процесса k= N, начальные условия задаются в качестве значений аргументов целевого утверждения-запроса. Параметры, характеризующие состояние процесса, вычисляются на каждой стадии рекурсии в процессе выполнения прямого хода.

В процессе выполнения прямого хода результат строится постепенно (хранит промежуточные значения) и окончательное значение приобретается в момент достижения терминальной ситуации. При обратном ходе результат теряется, так как восстанавливаются конкретизованные значения аргументов цели. Таким образом, в вершине доказательства результат отсутствует. Чтобы его не потерять, необходимо в момент достижения терминальной ситуации передать его значение переменной-результату, которую дополнительно необходимо включить в список аргументов. Избавиться от конкретики терминальной ситуации также можно введением еще одной переменной N в список аргументов, представляющей собой номер последнего шага процесса. С ее значением постоянно сравнивается номер текущего шага K, и при выполнении условия окончания процесса K= N достигается терминальная ситуация.

Список аргументов предиката, проектируемого при восходящей рекурсии, должен содержать две группы параметров: одна группа – исходные данные и результат, вторая – промежуточные значения переменных процесса.

Пример. Вычисление чисел Фибоначчи (вар.1)

F₁=1, F₂=2, F_n=F_n-1+_Fn-2.

Fib1(N,F):- fib2(N,F,1,1,0).

Fib2(N,F,N,F,_):-!.

Fib2(N,F,K,F1,F0):- K1=K+1, F2=F0+F1, fib2(N,F,K1,F2,F1).

Здесь N – порядковый номер элемента последовательности чисел Фибоначчи; F – число Фибоначчи.