一种递归算法比另一种更好，为什么？

Question

last/2有两个相似的算法。为什么 last_element0/2 比 last_element1/2 表现更好？使用额外的代码 last_element0/2 的性能几乎与 last/2 一样好，但不如 last_element1/2 优雅。此外，last_element1/2 会为太大的列表抛出堆栈溢出错误，但 last_element0/2 不会，为什么？最后，last_element1/2 有一个额外的选择点，因此有必要进行切割，不确定这是不是一个大问题。

last_element0(X,Last) :-
    last_element0(X,_,Last).

last_element0([X|Xs],_,Last) :-
    last_element0(Xs,X,Last).
last_element0([],Last,Last).

last_element1([_|Xs],Last) :-
    last_element1(Xs,Last),
    !.
last_element1([Last],Last).

测试结果如下：

last_element0/2

1 ?- length(Cs, 1000000), maplist(=(c), Cs),time(last_element0(Cs,X)).
% 1,000,003 inferences, 0.031 CPU in 0.023 seconds (136% CPU, 32000096 Lips)
Cs = [c, c, c, c, c, c, c, c, c|...],
X = c.

last_element1/2

2 ?- length(Cs, 1000000), maplist(=(c), Cs),time(last_element1(Cs,X)).
% 1,000,001 inferences, 0.250 CPU in 0.452 seconds (55% CPU, 4000004 Lips)
Cs = [c, c, c, c, c, c, c, c, c|...],
X = c.

last/2

3 ?- length(Cs, 1000000), maplist(=(c), Cs),time(last(Cs,X)).
% 1,000,001 inferences, 0.031 CPU in 0.022 seconds (142% CPU, 32000032 Lips)
Cs = [c, c, c, c, c, c, c, c, c|...],
X = c.

Answer 1

您的 last_element0/2 几乎与 library implementation of last/2 相同，至少对于 SWI-Prolog。它（多）快是因为，由于底层实现，last_element0/3（辅助谓词）的两个子句被认为是互斥的，因此不会创建选择点，也不需要丢弃选择点。

然而，看看这个：

?- last_element0(Xs, X).
ERROR: Out of local stack

?- last_element1(Xs, X).
ERROR: Out of local stack

?- last(Xs, X).
Xs = [X] ;
Xs = [_G1570, X] ;
Xs = [_G1570, _G1573, X] ;
% ... and so on

罪魁祸首：辅助谓词的子句顺序！

顺便说一句，还有其他定义方式 last/2:

last_reverse(List, Last) :- reverse(List, [Last|_]).
last_append(List, Last) :- append(_, [Last], List).

（无耻的自我推销）看到 and both answers for some more discussion about termination behavior, choice points, and efficiency (there are more links to follow there, too). I asked that question after answering a question on programmers.stackexchange，在这个过程中发现我什么都不知道。

一种递归算法比另一种更好，为什么？

One recursive algorithm better than the other, why?

optimization

recursion

prolog