我写了一个谓词 fib/2 来计算 Prolog 中的斐波那契数。虽然它有效，但它总是说“超出本地堆栈”，错误看起来像：
?- 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在第三个子句中添加或类似的规则
您可能会解决的一个问题是对斐波那契值进行不必要的重新计算。以下是您的代码的一个小改动，以解决此缺陷：
:- 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.
您的代码不是tail-recursive。适当的尾递归结构意味着可以应用 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) :-假的。fib(1, 1) :-假的。 纤维（N，NF）：- A 是 N - 1, B 是 N - 2， fib(A, AF), false ,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).
问题将得到解决。