Reputation: 4938
I am about to create program in Prolog that returns list of values from recurrence:
f(1) = 3, f(2) = 2, f(n) = f(n-1) * f(n-2)
E.g
rekur(5, S). -> S = [3, 2, 6, 12, 72]
I tried to solve it using:
rekur(2,[3,2]).
rekur(X,[H|T,M]):- X1 is X-1, rekur(X1,[H1,T1,M1], H1 is T*M.
Which has been proven to be completely wrong. Could you demonstrate the solution for this example? The explanation is highly appreciated. I have found that I have no idea how Prolog works. Thanks for the help.
Upvotes: 1
Views: 359
Reputation: 476758
A major problem is probably that [H|T,M]
is not a valid list. In fact a list in Prolog looks like what most programmers consider a linked list: it is a tuple containing a reference to the element (called the head) and a reference to the next tuple (called the tail). There is a special list []
which means end of list. [3,2]
is simply syntactical sugar for [3|[2|[]]]
which is actually nice formatting of [](3,[](2,[]))
.
Because of this linked list concept, you cannot (nor syntactically nor on O(1) access the last elements).
That's why Prolog usually works the other way around: you generate the head of the list, and by using recursion, the remainder of the list is filled in correctly. For your rekur/2
clause, you can work with two accumulators A
and B
that somehow store the next elements that will be emitted in the list. Furthermore you use the N
(the length of the list to be generated) as loop counter. For example:
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).
Upvotes: 2