Darlyn
Darlyn

Reputation: 4938

Recurrence in Prolog

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

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

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

Related Questions