递归Prolog程序执行顺序解析及回文谓词运行步骤问询

首先给出标准的递归回文谓词实现：

% 基例1：空列表是回文
palindrome([]).
% 基例2：单元素列表是回文
palindrome([_]).
% 递归规则：首尾元素相同，中间子串是回文
palindrome([First|Rest]) :-
    append(Middle, [First], Rest),
    palindrome(Middle).

一、分步执行过程（以palindrome([a,b,b,a])为例） #

我们一步步拆解这个调用的执行流程：

1. 首次调用palindrome([a,b,b,a])，由于列表长度大于1，匹配第三个递归规则：
   • 绑定First = a，Rest = [b,b,a]。
2. 执行子目标append(Middle, [a], [b,b,a])：
   • Prolog会寻找满足拼接条件的Middle，最终绑定Middle = [b,b]（因为[b,b] + [a] = [b,b,a]）。
3. 触发递归调用palindrome([b,b])，进入这个新的调用：
   • 列表长度仍大于1，匹配第三个规则，绑定First = b，Rest = [b]。
   • 执行子目标append(Middle, [b], [b])：
     • 找到Middle = []（因为[] + [b] = [b]）。
   • 触发更深层递归调用palindrome([])，匹配第一个基例，成功返回true。
4. 回到palindrome([b,b])的调用：
   • 内部递归调用成功，所以这个调用也成功返回true。
5. 回到最顶层的palindrome([a,b,b,a])调用：
   • 内部递归调用成功，整个谓词调用最终返回true。

如果测试非回文列表（比如palindrome([a,b,c])）：

• 首次调用匹配第三个规则，First=a，Rest=[b,c]。
• 执行append(Middle, [a], [b,c])时，Prolog找不到任何能满足拼接条件的Middle（因为[b,c]的末尾不是a），这个子目标失败。
• 回溯后没有其他规则可匹配，最终整个调用返回false。

二、核心疑问解答 #

1. 为什么append的第二个参数是[First]？ #

这是为了保证剩余列表的末尾元素等于首元素：
回文的核心特征是首尾字符相同，中间子串也是回文。Rest是原列表去掉首字符后的剩余部分，用append(Middle, [First], Rest)表示：把中间子串Middle和仅包含首字符的列表[First]拼接后得到Rest，这就强制Rest的最后一个元素必须是First，正好满足首尾相同的要求。同时Middle就是去掉原列表首尾字符后的中间子串，接下来只需要验证Middle是回文即可。

2. 递归调用时是否先完成内部palindrome再处理主调用？ #

是的，Prolog采用深度优先的执行策略：
当主调用中遇到递归的palindrome(Middle)时，会优先执行这个内部调用，包括它可能触发的所有更深层递归，只有当内部调用完全执行成功后，主调用才会继续后续逻辑（这里主调用在递归后没有其他子目标，所以直接成功返回）。如果内部调用失败，主调用会回溯尝试append的其他可能绑定（如果有的话），若没有其他可行解，整个主调用就会失败。

内容的提问来源于stack exchange，提问作者HS-Student