Aus lokalem Stapel versucht, Fibonacci-Funktion in Prolog

Question

zu testen Ich machte zwei verschiedene Fibonacci-Funktionen, die erste funktionierte perfekt. Dann habe ich versucht, es auf intuitive Weise zu vereinfachen. Ich dachte, es würde funktionieren, aber aus irgendeinem Grund heißt es FEHLER: Außerhalb des lokalen Stacks jedes Mal, wenn ich es teste.

Arbeitsversion:

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. 

Problem Version:

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

Könnte jemand mir erklären, was das Problem mit dem zweiten ist? Vielen Dank.

Answer 1

Ihr Problem ist, dass Sie in Ihrer zweiten rekursiv fibonacci/2 mit dem Begriff N-1 statt einer Ganzzahl aufrufen, deren Wert N-1 ist.

Also, zum Beispiel, wenn Sie fibonacci(3, F) aufrufen würde es in die dritte Klausel eingeben und fibonacci(3-1, F1) statt fibonacci(2, F1) aufrufen. Es würde dann wieder in die dritte Klausel eintreten und fibonacci(3-1-1, F1) aufrufen und so weiter.

Beachten Sie, dass Prolog den speziellen Operator is verwendet, um arithmetische Operationen auszuführen. Das erste Beispiel ist richtig.

Answer 2

Wäre das nicht einfacher? Definieren Sie fibonnaci\3 so, dass die ersten zwei Argumente die zwei 'Samen'-Elemente sind (normalerweise 1 und 1, obwohl sie beliebige zwei positive ganze Zahlen sein können). Das dritte Argument ist der berechnete Wert dieses Elements der Reihe.

Alles, was Sie tun müssen, ist ein Schiebefenster zu halten, wie Sie entlang der Fibonnaci Sequenz Rekursion, also:

% 
% 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.