为什么我在Prolog Fib/2中的谓词总是说“在局部堆栈之外”？
为什么我在Prolog Fib/2中的谓词总是说“在局部堆栈之外”？
提问于 2012-08-01 07:43:00
我用Prolog编写了一个谓词fib/2来计算斐波那契数。尽管它可以工作，但它总是显示"out of local stack“，错误看起来像这样：
?- 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. 提前感谢！
回答 4
Stack Overflow用户
回答已采纳
发布于 2012-08-01 07:49:29
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或类似的规则
Stack Overflow用户
发布于 2012-08-01 09:15:25
您可能要解决的一个问题是不必要地重新计算斐波那契数值。以下是对您的代码的一个小更改，以解决此缺陷：
:- 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.Stack Overflow用户
发布于 2012-08-02 02:03:55
您的代码不是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
.页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11750637
复制相关文章
相似问题
腾讯云开发者
