更深层次的Prolog计数解释

Question

目前在Prolog中玩...我在查看计数列表规则时遇到了麻烦.我无法在任何地方找到一个好的解释.有人可以在每次递归时给我一个细分吗？

count(0, []).
count(Count, [Head|Tail]) :-
    count(TailCount, Tail),
    Count is TailCount + 1.

一个地方说它是递归的(这对我来说是有意义的)而另一个地方说它不是.

Answer 1

它是递归的过程,但不是尾递归.编写尾递归过程是一种优化,允许系统将递归转换为迭代,避免无用的堆栈用于确定性计算(就像我们所说的那样).在这种情况下(BTW它与内置长度/ 2相同,只是交换了参数),我们可以使用累加器,并以这种方式重写过程:

count(C, L) :- count(0, C, L).

count(Total, Total, []).
count(SoFar, Count, [_Head|Tail]) :-
    Count1 is SoFar + 1,
    count(Count1, Count, Tail).

一些较旧的系统需要在递归调用之前进行剪切,以使优化有效:

    ...,
    !, count(Count1, Count, Tail).