本地堆棧試圖在Prolog中測試斐波那契函數

Question

我做了兩個不同的斐波那契函數，第一個函數完美工作。然後，我嘗試以直觀的方式簡化它。我認爲它會工作，但由於某種原因，它說ERROR：每次我測試它時都不在本地堆棧中。

工作版本：

fibonacci(0,0). 
fibonacci(1,1). 
fibonacci(N,F) :- N1 is N-1, N2 is N-2, fibonacci(N1,F1), fibonacci(N2,F2), F is F1+F2. 

不工作的版本：

fibonacci(0,0). 
fibonacci(1,1). 
fibonacci(N,F) :- fibonacci(N-1,F1), fibonacci(N-2,F2), F is F1+F2. 

有人能解釋我什麼是第二個問題呢？謝謝。

Answer 1

你的問題是，在你的第二個中遞歸調用fibonacci/2的術語N-1而不是一個整數值爲N-1。

因此，例如，如果您在調用fibonacci(3, F)時將輸入第三個子句，並調用fibonacci(3-1, F1)而不是fibonacci(2, F1)。然後它會再次進入第三個條款並呼叫fibonacci(3-1-1, F1)等等。

請注意，Prolog使用特殊運算符is來執行算術運算。 第一個例子是正確的。

Answer 2

難道這不是更簡單嗎？定義fibonnaci\3，使得前兩個參數是兩個「種子」元素（通常是1和1，儘管它們可以是任何兩個正整數）。第三個參數是該系列元素的計算值。

所有你需要做的當你沿着fibonnaci序列遞歸是維護一個滑動窗口，即：

% 
% the public interface predicate 
% 
fibonnaci(A , _ , A) . % 1. return the first element of the series 
fibonnaci(_ , B , B) . % 2. return the second element of the series 
fibonnaci(A , B , C) :- % 3. all subsequent values are the sum of 
    fib_body(A , B , C) . % the preceding two elements in the series. 

% 
% the 'private' worker predicate 
% 
fib_body(A , B , X) :- % 1. first, compute the next element of the series 
    X is A + B .   % as the sum of the preceding two elements. 
fib_body(A , B , X) :- % 2. on backtracking, shift our window 
    C is A + B ,   % and recurse down to get the next element 
    fib_body(B , C , X) . % in the series.