递归Prolog斐波那契公式产生错误的结果

Question

为什么fib(2,1)对这些Prolog代码行返回false ?

fib(1,F) :-
    F is 1.
fib(N,F) :-
    N > 1,
    fib((N-1),F1),
    F is F1.

Answer 1

首先，当N为2时，(N-1)是通过1的错误模式。你应该这样做

fib(N,F) :-
  N > 1,
  NM1 is N-1,
  fib(NM1,F).

第二:对于每个N，你的算法应该统一F和1。斐波那契公式非常不同;更像是

fib(0, 0).
fib(1, 1).
fib(N, F) :-
  N > 1,
  NM1 is N-1,
  NM2 is N-2,
  fib(NM1, FM1),
  fib(NM2, FM2),
  F is FM1+FM2.

第三:为了避免递归调用的指数爆炸问题，我建议使用不同的模式来计算斐波那契

fibH(0, 0, 0).
fibH(1, 1, 0).
fibH(N, F, FM1) :-
  N > 1,
  NM1 is N-1,
  fibH(NM1, FM1, FM2),
  F is FM1+FM2.
fib(N, F) :-
  fibH(N, F, _).

Answer 2

如果您的Prolog有表和大整数，

:- table fib/2.
fib(1, 1).
fib(2, 1).
fib(N, F) :-
  N > 2,
  N1 is N-1,  fib(N1, F1),
  N2 is N-2,  fib(N2, F2),
  F is F1+F2.

只要删除table/1指令就可以看到指数级的执行时间增长…