将尾递归序言代码重写为简单递归

Question

我是 prolog 的新手，我想练习将尾递归代码重写为简单的递归，以更好地理解该过程，但我没有成功。如果有人可以提供帮助，我将不胜感激。

注意：将尾递归（tail-call）代码转换为非尾递归代码通常在 Prolog 中不是明智之举。本题仅供学术学习之用。

代码：

some_predicate(T,1,3,0,D),
%the tail has elements with ID and Numbers like [(1,3),(2,5),(4,3)])
%in the D I count steps if different conditions are fulfilled
%I would like to write something like: some_predicate(T,1,3,D) without the Acc

some_predicate(_, _, 1, D, D):-!.
some_predicate([], _, _, D, D):-!.
some_predicate([(UP,_)|_], ID, H, D, D):-
    UP >= ID + H,
    !.
some_predicate([(UP,UH)|T], _, H, D, RetD):-
    H > UH,
    TH is H - 1,
    TD is D + 1,
    some_predicate(T, UP, TH, TD, RetD),
    !.
some_predicate([(UP,UH)|T], _, _,D, RetD):-
    TD is D + 1,
    some_predicate(T, UP, UH, TD, RetD),
    !.

我的尝试

some_predicate(_, _, 1,0):-!.
some_predicate([], _, _,0):-!.
some_predicate([(UP,_)|_], ID, H, 0):-
    UP >= ID + H,
    !.
some_predicate([(UP,UH)|Er], _, H, D):-
    H > UH,
    some_predicate(Er, UP, TH, TD),
    H is TH - 1,
    D is TD + 1,
    !.
some_predicate([(UP,UH)|Er], _, _,D):-
    some_predicate(Er, UP, UH, TD),
     D is TD + 1,
     !.

Answer 1

问题中的评论说您想在没有累加器的情况下重写代码，但是它不使用累加器。使用列表累加器的谓词的一般模式是这样的：

foo(X, Ys) :-
    foo(X, [], Ys).

foo(X, Acc, Acc) :-
    bar(X).
foo(X, Acc, Ys) :-
    baz(X, Y, Z),
    foo(Z, [Y | Acc], Ys).

涉及列表累加器的递归调用得到一个比以前的累加器更大的列表。在将累加器传递给递归调用之前，您向累加器添加一些内容。

您的程序改为使用 Prolog 中“列表迭代”的通用模式（欢迎使用更好的名称进行评论），它与使用累加器的递归相反：

foo([], Y) :-
    bar(Y).
foo([X | Xs], Y) :-
    baz(X),
    foo(Xs, Y).

（这里使用了和前面谓词类似的名字，但我并不是说它们是等价的。）

列表构造函数[_ | _]在子句的head中，而不是在递归调用中。递归调用中的列表比头部中的列表小。在将尾部传递给递归调用之前，您从列表中删除 某些内容。

因此，这不是您问题的答案，只是提示您需要从正确的地方开始：一些确实使用累加器列表的谓词定义。最简单有趣的案例可能是反转列表。

将尾递归序言代码重写为简单递归

Rewriting tail recursion prolog code into simple recursion

recursion

tail-recursion

prolog