为什么我在Prolog Fib/2中的谓语总是说"超出本地堆栈"？

Question

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

提前致谢!

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在第三个子句中添加或类似的规则