我写了一个谓词fib/2来计算Prolog中的Fibonacci数。尽管它有效，但它总是说"超出本地堆栈"，错误看起来像：
?- fib(10, F).
F = 55 ;
ERROR: Out of local stack
我的谓词如下：
fib(0, 0).
fib(1, 1).
fib(N, NF) :-
A is N - 1,
B is N - 2,
fib(A, AF),
fib(B, BF),
NF is AF + BF.
任何人都知道为什么会这样，以及如何修复它以获得以下内容：：
% or the search might stop immediately, without pressing space.
?- fib2(10, F).
F = 55 ;
false.
提前感谢！
out of local stack错误表示程序使用了太多内存，超出了分配的空间；当程序陷入无限循环时，这种情况经常发生。在您的情况下，以下是跟踪：
[trace] 2 ?- fib(2,M).
Call: (6) fib(2, _G671) ? creep
^ Call: (7) _G746 is 2+ -1 ? creep
^ Exit: (7) 1 is 2+ -1 ? creep
^ Call: (7) _G749 is 2+ -2 ? creep
^ Exit: (7) 0 is 2+ -2 ? creep
Call: (7) fib(1, _G747) ? creep
Exit: (7) fib(1, 1) ? creep
Call: (7) fib(0, _G747) ? creep
Exit: (7) fib(0, 0) ? creep
^ Call: (7) _G671 is 1+0 ? creep
^ Exit: (7) 1 is 1+0 ? creep
Exit: (6) fib(2, 1) ? creep
M = 1 ;
Redo: (7) fib(0, _G747) ? creep
^ Call: (8) _G752 is 0+ -1 ? creep
^ Exit: (8) -1 is 0+ -1 ? creep
^ Call: (8) _G755 is 0+ -2 ? creep
^ Exit: (8) -2 is 0+ -2 ? creep
Call: (8) fib(-1, _G753) ? creep
^ Call: (9) _G758 is -1+ -1 ? creep
^ Exit: (9) -2 is -1+ -1 ? creep
^ Call: (9) _G761 is -1+ -2 ? creep
^ Exit: (9) -3 is -1+ -2 ? creep
Call: (9) fib(-2, _G759) ? creep
^ Call: (10) _G764 is -2+ -1 ? creep
^ Exit: (10) -3 is -2+ -1 ? creep
...
正如你所看到的，在发现第二个斐波那契是1（根据你的定义）之后，你需要第二个解；由于您没有指定第三个子句只能在N>1 prolog试图通过计算fib（-1）、fib（-2）和fib（-3）等来找到第二个解决方案时使用。
要修复它，您必须将N>1或类似规则添加到第三子句
您可能要解决的一个问题是不必要的fibonacci值的重新计算。以下是对代码的一个小更改，以解决此缺陷：
:- dynamic db_fib/2.
init_fib :-
assertz( db_fib(0, 0) ),
assertz( db_fib(1, 1) ).
fib(N, NF) :-
A is N - 1,
B is N - 2,
get_fib(A, AF),
get_fib(B, BF),
NF is AF + BF.
get_fib(A, F) :-
db_fib(A, F),
!.
get_fib(A, F) :-
fib(A, F),
assertz( db_fib(A, F) ).
例如，在SWI Prolog中，可以计算
?- init_fib, fib(1000,F).
非常快速且无烟囱排气。
?- init_fib.
true.
?- fib(10,A).
A = 55.
?- fib(100,A).
A = 354224848179261915075.
?- fib(1000,A).
A = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
您的代码不是尾递归。适当的尾部递归结构意味着可以应用TRO（尾部递归优化）。通过重用递归调用的现有堆栈帧，这基本上将递归转换为迭代。应用TRO后，每个递归调用都会在调用堆栈上推送一个新的堆栈帧。你应该像这样构建你的谓词（注意，我还没有真正测试过这个代码，但它应该能完成任务）：
% ------------------------------------------------------
% the public interface predicate
% ------------------------------------------------------
fib(1,1). % first element in the sequence is 1
fib(2,1). % second element in the sequence is 1
fib(N,X) :- % subsequent elements
N > 2 , % where N > 2
fib(1,1,3,N,X) % are computed
.
% --------------------------------------
% the private worker predicate for N > 2
% this predicate maintains a sliding 'window' on the fibonacci sequence
% as it computes it
% --------------------------------------
fib( V1 , V2 , N , N , X ) :- % compute the element at position N
N > 2 , % ensure N > 2
X is V1 + V2 % value is the sum of the 2 prior elements
.
fib( V1 , V2 , T , N , X ) :- % on backtracking, slide the window to the right:
T > 2 , % ensure N > 2
T1 is T + 1 , % increment N
V3 is V1 + V2 , % compute the next value (V1+V2)
fib(V2,V3,T1,N,X) % recurse
.
只考虑程序的一个片段，称为失败切片，可以通过将false目标添加到程序中来获得，从而最好地了解程序不终止的原因。
fib（0，0）：-false。 fib（1，1）：-false。fib（N，NF）：-A是N-1，B是N-2，fib（A，AF），假， fib（B，BF）， NF为AF+BF。
您程序的所有罢工部分对终止没有任何影响。它们可能会产生其他影响，比如你的项目会成功或失败，但在终止时没有。
要使程序终止，必须更改可见部分中的某些内容。很明显，第一个自变量是无限减少的。
但故障切片也意味着许多其他程序将有效地具有相同的故障切片。例如，考虑把事实放在最后（正如@RicardoMojica所建议的那样）。这些事实可以用false以完全相同的方式删除，从而产生相同的程序。因此：
改变条款的顺序对（普遍的）终止没有影响。
有限保修
所有这些声明仅适用于纯单调程序。不纯的非单调特征和副作用破坏了这些性质
如果是这样写的，最有可能是订单（谁先是鸡还是蛋）：
fib(N, NF) :-
A is N - 1,
B is N - 2,
fib(A, AF),
fib(B, BF),
NF is AF + BF.
fib(1, 1).
fib(0, 0).
这个问题将会得到解决。