Prolog 上的递归

Question

我正在尝试编写一个 Prolog 递归，它将 return 以下数字表示形式：

1 --> s(0)

2 --> s(s(0))

3 --> s(s(s(0))) ...

我使用了以下代码：

retnum(s(0),1). %Stop Condition
retnum(S,Z):-
    retnum(s(S),Z1),
    Z is Z1+1.

但是当我尝试运行预测时：

retnum(A,2).

我得到结果 A=0，如果我继续，我会收到超出卡住限制的错误。我期望得到结果 A = s(s(0))。我还尝试添加额外的停止条件：retnum(0,0).

知道我的错误在哪里吗？是否有更好的方法？

Answer 1

您使用的递归调用不正确。递归实例的参数应该小于原始参数（更一般地说：收敛到边界条件）。这可能会给你你想要的：

retnum(s(0), 1).
retnum(s(S), Z) :-
    retnum(S, Z1),
    Z is Z1 + 1.

但这更好。

retnum1(s(0), 1).
retnum1(s(S), Z) :-
    Z > 1, Z1 is Z - 1,
    retnum1(S, Z1).

尝试trace/0看看为什么会这样。

Answer 2

按照@false 的建议，最好的方法是使用library(clpfd)。但是，如果您不想使用该库，一个可能的解决方案是考虑两种不同的情况：

确定性情况 [要转换成Peano形式的自然N是常数]：从N，递归递减这个值，直到达到值0（可以生成唯一解）。
非确定性情况 [要转换为 Peano 形式的自然 N 是一个变量]：从0，递归增加这个值，在每一步产生一个新的自然N（可以产生无限多的解）。

% nat(?Natural, ?Peano)

  nat(N, P) :-
     (  integer(N) -> nat_det(N, P)
     ;  var(N)     -> nat_nondet(N, P)).

  nat_det(0, 0) :- !.
  nat_det(N, s(P)) :-
     succ(M, N),
     nat_det(M, P).

  nat_nondet(0, 0).
  nat_nondet(N, s(P)) :-
     nat_nondet(M, P),
     succ(M, N).

这里有一些例子：

?- nat(2, P).
P = s(s(0)).

?- nat(2, s(s(0))).
true.

?- nat(2, s(s(s(0)))).
false.

?- nat(N, s(s(s(0)))).
N = 3.

?- N = 4, nat(N, P).
N = 4,
P = s(s(s(s(0)))).

?- nat(N, P), N = 4, !. % we know that there exist only one solution!
N = 4,
P = s(s(s(s(0)))).

?- nat(N, P).
N = P, P = 0 ;
N = 1,
P = s(0) ;
N = 2,
P = s(s(0)) ;
N = 3,
P = s(s(s(0))) ;
...

Prolog 上的递归

Recursion on Prolog

recursion

prolog

successor-arithmetics