为何Prolog执行数组反转代码时会陷入无限循环？

你写的Prolog逆序函数在判断两个列表是否互为逆序时没问题，但如果用变量接收逆序结果，按下;想确认有没有其他结果时，程序会直接陷入无限循环。原代码如下：

rev([],[]).
rev([X|A],B):- append(C,[X],B), rev(A,C) .

测试时，rev([4,3,9,9],Result)能返回正确的逆序列表，但继续输入;后就会一直卡着不动。

问题出在哪 #

原代码靠append(C,[X],B)把B拆成“前面的C”加“末尾的X”，再递归处理A和C。当第一个参数是固定长度的列表、第二个参数是变量时：

1. 第一次递归能生成正确结果，因为后续的rev(A,C)会约束C的长度必须和A一致。
2. 但回溯的时候，Prolog会尝试append的其他拆分方式——比如让C变成更长的列表，哪怕后面的递归根本满足不了A和C的长度匹配。而append可以无限生成更长的C，导致递归永远停不下来，直接陷入死循环。

怎么修复 #

换用累加器的写法，逻辑更直接，还能避免无效的回溯分支：

rev(List, Rev) :-
    rev_acc(List, [], Rev).

rev_acc([], Acc, Acc).
rev_acc([H|T], Acc, Rev) :-
    rev_acc(T, [H|Acc], Rev).

测试效果 #

• 判断逆序：rev([4,3,9,9],[9,9,3,4])返回true ; false，正常工作。
• 生成逆序：rev([4,3,9,9],Result)返回Result = [9, 9, 3, 4] ; false，按下;后直接返回false，不会无限循环。

为啥这个写法行 #

累加器版本是尾递归，每一步把当前列表的头元素放到累加器的最前面，等原列表空了，累加器就是逆序结果。整个过程没有多余的回溯分支，Prolog不会瞎尝试无效的拆分，自然也就不会卡死。

内容的提问来源于stack exchange，提问作者iiMouad