Можно ли сделать это хвостовой рекурсией в Прологе? - PullRequest
Новая
       381

Можно ли сделать это хвостовой рекурсией в Прологе?

5 голосов
/ 23 октября 2011

Я изучаю Пролог, и в качестве упражнения я экспериментирую с простой базой данных, которая вычисляет сумму всех чисел до заданного числа (т.е. 0 = 0, 1 = 1, 2 = 3, 3 = 6, 4 = 10, ...). Достаточно просто: 

counting_sum(0, 0).
counting_sum(Num, Sum) :- Num > 0, PrevNum is Num - 1,
    counting_sum(PrevNum, PrevSum), Sum is Num + PrevSum.

Это взрывается где-то около counting_sum(150000, X). с переполнением стека. Я понимаю, что Пролог может выполнять хвостовую рекурсию, но если я перенесу рекурсивный вызов в конец правила, я получу 

error(instantiation_error,(is)/2)

, который, как я предполагаю, говорит мне, что я не могу использовать PrevSum, пока он не был объединен с counting_sum(PrevNum, PrevSum). Это правильно, и есть ли способ сделать этот хвост рекурсивным? Я использую GNU Prolog 1.3.1, если это что-то меняет.

P.S. Я все еще шаткий по терминологии. Дайте мне знать, если я неправильно использовал термины.

1 Ответ

8 голосов
/ 23 октября 2011

Попробуйте что-то вроде этого (используйте аккумулятор): 

counting_sum(Count, Sum):-
  counting_sum(Count, 0, Sum).

counting_sum(0, Sum, Sum).
counting_sum(Num, PrevSum, Sum):- Num > 0, PrevNum is Num - 1,
    NextSum is PrevSum + Num,
    counting_sum(PrevNum, NextSum, Sum).
...