Prolog 递归函数未按预期运行

Question

我正在尝试在 Prolog 中实现斐波那契数列的递归版本。下面是代码：

fib(0,F) :- F is 0.
fib(1,F) :- F is 1.
fib(N,F) :- N > 1,
AA is (N - 1),
BB is (N - 2),
fib(AA,CC),
fib(BB,DD),
RR is (CC + DD),
F == RR,
F is RR.

问题是它的行为并不符合我的逻辑预期。当我使用 trace 调用 fib(3,2) 时，我得到以下几行：

   Call: (7) fib(3, 2) ? creep
   Call: (8) 3>1 ? creep
   Exit: (8) 3>1 ? creep
   Call: (8) _G2569 is 3+ -1 ? creep
   Exit: (8) 2 is 3+ -1 ? creep
   Call: (8) _G2572 is 3+ -2 ? creep
   Exit: (8) 1 is 3+ -2 ? creep
   Call: (8) fib(2, _G2573) ? creep
   Call: (9) 2>1 ? creep
   Exit: (9) 2>1 ? creep
   Call: (9) _G2575 is 2+ -1 ? creep
   Exit: (9) 1 is 2+ -1 ? creep
   Call: (9) _G2578 is 2+ -2 ? creep
   Exit: (9) 0 is 2+ -2 ? creep
   Call: (9) fib(1, _G2579) ? creep
   Call: (10) _G2578 is 1 ? creep
   Exit: (10) 1 is 1 ? creep

引起我注意的是最后一个调用，Call: (10)，它说“_G2578 是 1？”，尽管我调用的是 fib(1, _G2579)。我的预期是 _G2579 将被更改，但情况似乎并非如此。我需要找出原因，因为我高度怀疑这就是 fib(3,2) 返回 false 而不是 true 的原因。

Answer 1

如果我没记错的话，问题出在

F == R

检查 F（新引入的没有值的术语）是否等于 R。

如果你改变它在

F = R

所以将 F 与 R 统一起来（在 F is R 之后是多余的），你的 fib/2 应该可以工作。

不过我建议你简化一下。

(1) terminale case fib(0,F) :- F is 0. 很好，但你可以写成

fib(0,0).

(2) 对另一个终端情况的简化：你可以把它写成

fib(1,1).

(3) 在一般子句中，不需要具有相同（统一）值的两个不同变量 F 和 RR；您只能通过以下方式使用 F

fib(N,F) :-
  N > 1,
  AA is (N - 1),
  BB is (N - 2),
  fib(AA,CC),
  fib(BB,DD),
  F is (CC + DD).

Prolog 递归函数未按预期运行

Prolog recursive function not behaving as expected

recursion

trace

prolog

fibonacci