Search code examples
recursionprologarithmetic-expressionsinstantiation-error

Prolog:: f(x) recursion

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)?

Solution

  • The issue is that you are trying to evaluate f(X-1,Y) as if it were a number, but of course it is a predicate that may be true or false. After some tinkering, I found this solution:

    f(1,1).
f(X,Y) :- X > 0, Z is X-1, f(Z,N), Y is 5*X + X*X + N.

    The trick is to let it find its way down to f(1,N) first, without evaluating anything; then let the results bubble back up by satisfying Y is 5*X + X*X + N. In Prolog, order matters for its search. It needs to satisfy f(Z,N) in order to have a value of N for the statement Y is 5*X + X*X + N.

    Also, note the condition X > 0 to avoid infinite recursion.