Prolog:: f(x) recursion

Question

I'm a beginner to Prolog and have two requirements:

1. f(1) = 1

2. f(x) = 5x + x^2 + f(x - 1)

rules:

f(1,1). f(X,Y) :- Y is 5 * X + X * X + f(X-1,Y).

query:

f(4,X).

Output:

ERROR: is/2: Arguments are not sufficiently instantiated

How can I add value of f(X-1)?

Answer 1

This can be easily solved by using auxiliary variables.

For example, consider:

f(1, 1).
f(X, Y) :-
        Y #= 5*X + X^2 + T1,
        T2 #= X - 1,
        f(T2, T1).

This is a straight-forward translation of the rules you give, using auxiliary variables T1 and T2 which stand for the partial expressions f(X-1) and X-1, respectively. As @BallpointBen correctly notes, it is not sufficient to use the terms themselves, because these terms are different from their arithmetic evaluation. In particular, -(2,1) is not the integer 1, but 2 - 1 #= 1 does hold!

Depending on your Prolog system, you may ned to currently still import a library to use the predicate (#=)/2, which expresses equality of integer expressesions.

Your example query now already yields a solution:

?- f(4, X).
X = 75 .

Note that the predicate does not terminate universally in this case:

?- f(4, X), false.
nontermination

We can easily make it so with an additional constraint:

f(1, 1).
f(X, Y) :-
        X #> 1,
        Y #= 5*X + X^2 + T1,
        T2 #= X - 1,
        f(T2, T1).

Now we have:

?- f(4, X).
X = 75 ;
false.

Note that we can use this as a true relation, also in the most general case:

?- f(X, Y).
X = Y, Y = 1 ;
X = 2,
Y = 15 ;
X = 3,
Y = 39 ;
X = 4,
Y = 75 ;
etc.

Versions based on lower-level arithmetic typically only cover a very limited subset of instances of such queries. I therefore recommend that you use (#=)/2 instead of (is)/2. Especially for beginners, using (is)/2 is too hard to understand. Take the many related questions filed under instantiation-error as evidence, and see clpfd for declarative solutions.