Recurrence results stored in list in Prolog

Question

I am trying to create a Prolog program for solving the recurrent equation:

f(1)=2, f(2)=5, f(n)=f(n-1)+2*f(n-2)

I managed with the rec function below, but I have trouble when I want to store the result in the list (by function recList).
This is my implementation:

rec(1,2).
rec(2,5).
rec(X,N) :- X1 is X-1, X2 is X-2, rec(X1,N1), rec(X2,N2), N is N1+2*N2.

recList(0,[]).
recList(X,[N|L]) :- rec(X,N), X1 is X-1, recList(X1,L).

My implementation of recList works for calling it by the first value

?- recList(4,X). 

->

X = [19, 9, 5, 2] .

but it doesn't when I call it by the second one if it is longer than two elements:

?- rekurList(X,[2]).
X = 1 .

?- rekurList(X,[5,2]).
X = 2 .

?- rekurList(X,[9,5,2]).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [9] rec(_12587334,9)
ERROR:    [8] rekurList(_12587360,[9,5|...]) at /locaiton/rec.pl:6
ERROR:    [7] <user>

What is wrong, please?

Answer 1

The predicate is/2 fails because is/2 evaluates the right-hand structure as an arithmetic expression. If it is not a valid arithmetic expression or a number, is/2 fails. So when you call

recList(X, [19, 9, 5, 2]).

you get rec/2: Arguments are not sufficiently instantiated. If you run the tracer (in SWISH, which is SWI on line: trace, recList(X, [19, 9, 5, 2]). In ECLiPSe you can use tkeclipse Tools->Tracer) you get something like:

Call:recList(_13806, [19, 9, 5, 2])
 Call:rec(_13806, 19)
 Call:_14048 is _13806+-1
 Exception:_14102 is _13806+-1
is/2: Arguments are not sufficiently instantiated

To solve this problem you can use the library clpfd in this way (i wrote the solution using SWI):

:- use_module(library(clpfd)).

rec(1,2).
rec(2,5).
rec(X,N):- 
    X1 #> 0,
    X1 #= X-1, 
    rec(X1,N1),
    X2 #> 0,
    X2 #= X-2,  
    rec(X2,N2),
    N #= N1+2*N2, !. %notice the cut (!)

recList(0,[]):-!.
recList(X,[N|L]):- 
    rec(X,N), 
    X1 #= X-1, 
    recList(X1,L).

Query:

?- recList(X, [19, 9, 5, 2]).
X = 4.
false.

?- recList(4,L).
L = [19, 9, 5, 2]
false

Note that the cut ! is needed because otherwise, after the first solution, if you click more, the computation will never end. Also X1 #> 0 and X2 #> 0 are needed because otherwise you get a out of local stack error.