2

I'm a Prolog beginner and I'm looking for a way to reverse the output of this code.

fib(N, F) :- fib(N, 0, [1], F).
fib(0, _, A, A).
fib(N, A, [B|Bs], F) :- N1 is N - 1, Sum is A + B, fib(N1, B, [Sum,B|Bs], F).

The code calculates the Fibonacci numbers for the value of N and prints the result in F.

For example fib(4,X). produces X=[5,3,2,1,1]. What I want is X=[1,1,2,3,5] (reversed output).

I can't seem to bring it to this format, and preserve its tail recursive property.

thanks for any help

1 Answer 1

0

If you just want to reverse the list at the end, use reverse/2:

fib(N, F) :- fib(N, 0, [1], FRev), reverse(FRev, F).

If you want to built the list in the reversed order, you would have to rethink the clauses. One solution is to use last/2 and append/3 to put new elements at the end of the accumulator, not in front of it.


After returning the first solution, Prolog tries to find a second one and you probably get an error:

?- fib(5, F).
F = [8, 5, 3, 2, 1, 1] ;
ERROR: Out of global stack

That happens because for a goal fib(0, ...) Prolog uses the first rule, but creates a choice point and it backtracks to it later. From that point the stack is filled with goals: fib(-1,...), fib(-2,...), etc. None of these will be ever satisfied. You should put a cut operator in the first clause for fib/4:

fib(0, _, A, A):-!.

so it would not try to resatisfy fib(0,...) using the second rule.

?- fib(5, F).
F = [8, 5, 3, 2, 1, 1].
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.