Python编写递归回文识别函数 偶数长度回文判定异常咨询

你对偶数长度回文判定错误的根源是递归终止的边界条件设置错误：

• 现有代码在字符串长度为0时返回False，但偶数长度的回文在逐层剥离首尾匹配字符的递归过程中，最终一定会走到空字符串的状态。
• 以daad的实际执行流程为例：
  1. 第一层传入daad，首尾字符都是d，匹配成功，进入下一层传入截掉首尾的aa
  2. 第二层传入aa，首尾字符都是a，匹配成功，进入下一层传入截掉首尾的空字符串
  3. 走到空字符串分支，代码直接返回False，最终错误判定daad不是回文。
• 奇数长度的回文（比如racecar）之所以能正常判定，是因为递归剥离到最后会触发长度为1的单字符分支，直接返回True，不会走到空字符串的判断分支，所以之前的错误逻辑没有暴露。

空字符串本质是所有首尾字符都完成匹配的合法递归终止态，应当返回True，只需要调整原代码中len(s)==0分支的返回值即可修正问题：

def palindrome(s):
    if len(s) == 0:
        return True  # 原代码此处返回False，是错误根源
    elif len(s) == 1:
        return True
    elif len(s) > 1:
        if s[0] == s[-1]:
            return palindrome(s[1:-1])
        else:
            return False

修正后的代码逻辑可以进一步简化，将长度为0、1的同返回值分支合并，减少冗余判断：

def palindrome(s):
    # 长度小于等于1的场景，均为匹配完成的合法状态
    if len(s) <= 1:
        return True
    # 首尾字符不匹配直接判定为非回文
    if s[0] != s[-1]:
        return False
    # 匹配成功则递归处理内部子串
    return palindrome(s[1:-1])

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