[我在几个程序中玩着permutation，偶然发现了这个小实验：
排列方法1：
permute([], []).
permute([X|Rest], L) :-
permute(Rest, L1),
select(X, L, L1).
排列方法2：
permute([], []).
permute(L, [P | P1]) :-
select(P, L, L1),
permute(L1, P1).
排列方法3（使用内置方法：]：
permute(L, P) :- permutation(L, P).
我知道使用尾递归是一种很好的做法，通常使用内置函数是有效的。但是当我运行以下命令时：
time(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).
我得到以下结果，这些结果在多个运行中相对一致：
方法1：
% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)
方法2：
% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)
方法3：
% 2,959,245 inferences, 1.967 CPU in 4.217 seconds (47% CPU, 1504539 Lips)
因此，非尾递归方法的实时性明显更高。
在其他所有条件相同的情况下，特定的递归类型通常更实时有效吗（我知道这并不总是一个简单的前提）？该实验告诉我，我可能不希望一直追求尾递归，但是我可能需要先进行性能分析，然后再权衡性能收益与尾递归所具有的其他收益。
非常好的问题，+ 1！
Tail调用（并且在特殊情况下，tail recursion）优化仅在谓词为deterministic时才适用！这里不是这种情况，因此您的谓词将始终需要本地堆栈空间，无论您按什么顺序放置目标。生成所有解决方案时，非尾递归版本在此具有更高的（时间）效率，因为它需要在回溯上进行较少的统一。
EDIT：在这一点上，我正在扩展，因为值得更详细地研究性能差异。
首先，为清楚起见，我重命名了两个不同的版本，以明确说明我在谈论哪个版本：
变量1：非尾递归：
permute1([], []).
permute1([X|Rest], L) :-
permute1(Rest, L1),
select(X, L, L1).
Variant 2：尾递归：
permute2([], []).
permute2(L, [P|P1]) :-
select(P, L, L1),
permute2(L1, P1).
再次注意，尽管第二个版本显然是尾部递归的，但是尾部调用（以及尾部递归）优化仅在谓词为deterministic时才有用，因此在生成所有排列时无济于事，因为在这种情况下仍会留下选择点。
也请注意，我故意保留原始变量的命名和主谓词名称，以避免引入更多的变体。就个人而言，我更喜欢使用一种命名约定，该命名约定通过将s附加到其变量上来明确表示哪个变量表示lists，这类似于常规的英语复数形式。同样，我更喜欢谓词名称，使其更清楚地展现代码的（至少是预期的和合意的）声明性，关系性质，并出于这个原因，建议避免使用命令性名称。
现在考虑展开第一个变体，并部分评估它以获得3个元素的列表。我们从一个简单的目标开始：
?- Xs = [A,B,C], permute1(Xs, L).
，然后通过插入permute1/2的定义逐步展开它，同时使所有磁头统一变得明确。在第一次迭代中，我们获得：
α-Xs＝ [A，B，C]，Xs1 ＝ [B，C]，permute1（Xs1，L1），选择（A，L，L1）。
我用粗体标记了头部的统一。
[现在，还剩下permute1/2的一个目标。因此，我们重复该过程，再次插入谓词唯一适用的规则主体来代替其头部：
α-Xs = [A，B，C]，Xs1 = [B，C]，Xs2 = [C]，permute1（Xs2，L2），select（B，L1，L2），select（A， L，L1）。
再通过一次，我们得到：
？-Xs = [A，B，C]，Xs1 = [B，C]，Xs2 = [C]，select（C，L2，[]），select（B，L1，L2），选择（A，L，L1）。
如果我们只是反复展开permute1/2的定义，这就是最初的目标。
现在，第二个变种呢？同样，我们从一个简单的目标开始：
?- Xs = [A,B,C], permute2(Xs, Ys).
展开permute2/2的一次迭代将产生等效的版本：
α-Xs＝ [A，B，C]，＜[Ys ＝ [P | P1]，选择（P，Xs，L1），permute2（L1，P1）。和第二次迭代产生：
α-Xs = [A，B，C]，
Ys = [P | P1]，select（P，Xs，L1），Ys1 = [P1 | P2]，select（P1，L1 ，L2），permute2（L2，P2）。我将第三次也是最后一次迭代作为一个简单的练习，
强烈建议您这样做。
head unifications
有很大的不同，第一个版本在开始时就确定地执行，第二个版本在开始时执行over and在回溯上]]。这个著名的例子很好地表明，如果代码不是确定性的，尾部递归的速度可能会很慢，这与通常的预期有点相反。sum/2 using an accumulator，而不是。 sum/2的例子很简单。一个版本在堆栈上进行算术运算，另一个版本使用累加器。但是，就像现实世界中的大多数事物一样，普遍的真理是“取决于情况”。例如，使用完整实例比较方法1和2的效率：