В самом общем виде рекурсия есть способ разбиения задачи на подзадачи, каждая из которых является уменьшенным вариантоми предыдущей. В итоге мы должны прийти к задаче, решаемой непосредственно.
Решить ее позволит утверждение, называемое ГРАНИЧНЫМ УСЛОВИЕМ.
В задаче о вычислении суммы таким условием является
sum_series2(1,1) :- !.
Для ответа на запрос sum_series2(4,X) последовательно вычислялись sum_series2(3,S1), sum_series2(2,S2), sum_series2(1,S3) (граничное условие).
Такая рекурсия называется НИСХОДЯЩЕЙ.
Поступим наоборот: начнем с граничного условия и будем строить решение, пока не получим исходную задачу.
Такая рекурсия называется ВОСХОДЯЩЕЙ.
В таком методе правило sum_series3 должно иметь два дополнительных параметра:
1) указание на размер решенной к данному моменту задачи (число уже просуммированных слагаемых);
2) запись промежуточного решения (уже подсчитанной частичной суммы).
Запрос
sum_series3(1,1,7,X)
включает старое граничное условие, как уже решенную к настоящему моменту задачу.
Новое граничное условие выглядит так:
sum_series3(N,X,N,X):-!.
Правило 3 рекурсии:
/* M-текущее слагаемое, S-частичная сумма, N-последнее слагаемое, X-окончательная сумма */
sum_series3(M,S,N,X):-
M1=M+1,
S1=S+M1,
sum_series3(M1,S1,N,X).
Упражнение 5.2.
Вычислить и напечатать факториал числа 5 с помощью восходящей и нисходящей рекурсии.
