为何回文判断Python递归代码中check返回True但最终结果为False

问题根源 #

你写的check递归函数缺少返回值语句：当s[start] == s[end]进入下一层递归时，你直接调用了check(s, start + 1, end - 1)，但没有把递归调用的结果返回给上层调用方。Python中函数如果没有显式写return语句，默认会返回None，None在布尔判定中等价于False，这就是明明内层触发start > end返回了True，外层最终拿到的结果却是False的原因。

修复方案 #

只需要给check函数的递归调用加上return即可，修改后的完整代码如下：

def isPalindrome(self, s: str) -> bool:
    cleanString = s.lower()
    cleanString = ''.join(filter(str.isalpha, cleanString))     
    if len(cleanString) <= 1: # 这里优化了边界判断，空字符串也属于回文
        return True
    start = 0
    end = len(cleanString)-1
    return check(cleanString, start, end)
        
def check(s: str, start: int, end: int) -> bool:
    print(f'{s[start]} {start} : {s[end]} {end}')
    if start > end:
        return True
    if s[start] != s[end]:
        return False
    # 新增return，把递归结果返回上层调用
    return check(s, start + 1, end - 1)

print(isPalindrome("A man, a plan, a canal: Panama"))

补充说明 #

• 原测试用例清洗后得到的字符串是amanaplanacanalpanama，本身确实是回文，修复后运行代码会返回正确结果True。
• 边界判断优化为len(cleanString) <= 1后，可以兼容输入为空、或者清洗后得到空字符串的场景，这类场景也符合回文定义。

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