prolog - 为什么我在 Prolog Fib/2 中的谓词总是说 "out of local stack"？

Question

我写了一个谓词 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. 

提前致谢!

Answer 1

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或类似于第三条的规则