在Prolog中計算斐波那契數列，尾遞歸

Question

我想在遞歸尾模式下計算Prolog中的斐波納契數列。

fibonacci(0,0). 
fibonacci(1,1). 
fibonacci(N,Result) :- 
    fibonacci(N,1,0). 

fibonacci(N,Result,Count) :- 
    Count < N, 
    !, 
    Count1 is Count + 1, 
    Result1 is Result + Count, 
    fibonacci(N,Result1,Count1). 
fibonacci(N,Count,Count). 

但結果不正確，是什麼問題？

Answer 1

在行Result1 is Result + Count你只添加計數變量結果並添加0,1,2，...但在斐波那契你需要添加兩個以前的例如0,1，（1 + 0 = 1），（ 1 + 1 = 2），.... 我建議此實現：

fib(0, 0). 
fib(1, 1). 
fib(N,Result):-fibonacci(N,0,1,Result). 

fibonacci(0,N,_,N). 
fibonacci(N, Prev1,Prev2,Result):- 
    N>0, 
    New_Prev2 is Prev1+Prev2, 
    N1 is N-1, 
    fibonacci(N1,Prev2,New_Prev2,Result). 

Answer 2

這裏是一個尾遞歸solution.You需要使用一個累加器。本質上你是計算斐波納契向後。當你達到1你停止。

斐波納契（0,0）。
斐波納契（N，結果）： -
N> 0，
fib（N，0,1，結果）。

fib（1，_，Accum，Accum）。
fib（N，Val，Accum，Result）： -
N1是N-1，
AccumNew是Val + Accum，
fib（N1，Accum，AccumNew，Result）。