Search code examples
prologinfinite-loopfibonaccifailure-slice

I am trying to write a prolog program for fibbonaci series.This code is going in infinite loop .Can someone tell what's the error?

fib(0,0).   
fib(1,1).  
fib(A,Result):-    
    fib(A-1,R),  
    fib(A-2,P),  
    Result is R+P.
Solution

  • To understand why, first narrow down the reason for non-termination. Here is the smallest part of your program that still loops:

    fib(0,0) :- false.
fib(1,1) :- false.
fib(A,Result):-    
    fib(A-1,R), false,
    fib(A-2,P),  
    Result is R+P.

    No matter what the arguments are, this program will loop. And thus your original program will loop too.

    To fix this you need to change something in the visible part: You need to ensure that A > 1. In this manner the program now terminates.

    Further, as noted correctly by @andsanmar, A-1 alone is not a number, but just the term -(A,1) so it can never be 0 nor 1. So either write

    fib(N,0) :- N =:= 0.
fib(N,1) :- N =:= 1.
...

    Or add (is)/2 as suggested by @andsanmar.

    For more on how to narrow down reasons for non-termination see .