Восходящая рекурсия - промежуточные результаты вычисляются на некоторой стадии рекурсии, так что ответ строится постепенно и передается в виде параметра рабочей памяти до тех пор. пока не будет достигнута некоторая ( терминальная ) ситуация. К этому моменту ответ уже готов, и нужно передать его вызывающей функции верхнего уровня.
Пример 1
Код на Lisp /*Вычисление длины списка с помощью восходящей рекурсии */ domains sl = symbol* nl = integer* predicates list_len ( sl, integer ) list_len ( nl, integer ) l_l ( sl, integer, integer ) l_l ( nl, integer, integer ) clаuses list_len ( X, N ) :- l_l ( X, N, 0 ). l_l ( [ ], N, N ). l_l ( [ _ | R ], N, N1 ) :- N2 = N1 + 1, l_l ( R, N, N2 ).
В некоторых случаях, при использовании рекурсии, результат вычисляется по-разному, следовательно, он зависит от выбора вида рекурсивной функции.
Пример 2:
Код на Lisp /*Копирование списка с помощью разных видов рекурсии */ // список копируется в обратном порядке – рекурсия восходящая. ucopy ( W, S ) : - cop ( W, [ ] ). cop ( [ ], S ). cop ( [ X | Y ], [ X | _ ] ) : - cop ( Y, S ).
|
Выход