Рецидив в Прологе

Question

Я собираюсь создать программу на Прологе, которая возвращает список значений из повторения:

f(1) = 3, f(2) = 2, f(n) = f(n-1) * f(n-2) 

Например

rekur(5, S). -> S = [3, 2, 6, 12, 72] 

Я пытался решить с помощью:

rekur(2,[3,2]). 
rekur(X,[H|T,M]):- X1 is X-1, rekur(X1,[H1,T1,M1], H1 is T*M. 

Что было доказано, что оно полностью ошибочно. Не могли бы вы продемонстрировать решение для этого примера? Объяснение очень ценится. Я обнаружил, что понятия не имею, как работает Prolog. Спасибо за помощь.

Answer 1

Важной проблемой является, вероятно, то, что [H|T,M] не является допустимым списком. На самом деле список в Prolog выглядит так, как большинство программистов считают связанным списком: это кортеж, содержащий ссылку на элемент (называемый головой) и ссылку на следующий кортеж (называемый хвостом ). Существует специальный список [], что означает конец списка. [3,2] - это просто синтаксический сахар для [3|[2|[]]], который на самом деле хороший формат [](3,[](2,[])).

Из-за этой концепции связанного списка вы не можете (ни синтаксически, ни на O (1) доступ к последним элементам).

Вот почему Prolog обычно работает наоборот: вы создаете голову списка, и с помощью рекурсии остаток списка заполняется правильно. Для вашего предложения rekur/2 вы можете работать с двумя аккумуляторами A и B, которые каким-то образом сохраняют следующие элементы, которые будут выбраны в списке. Кроме того, вы используете N (длину списка, который должен быть сгенерирован) в качестве счетчика циклов. Например:

rekur(N,L) :- 
    rekur(N,3,2,L). 

rekur(N,_,_,[]) :- 
    N <= 0, 
    !. 
rekur(N,A,B,[A|T]) :- 
    N > 0, 
    C is A*B, 
    N1 is N-1, 
    rekur(N1,B,C,T).