python - 理解递归和多重返回

Question

我正在学习 OpenCourseWare 上的麻省理工学院 6.00 类(class)，但我在递归讲座上遇到了一些麻烦。我想我理解基本的想法，你可以把一些问题分解成更小的、可重复的问题。我遇到麻烦的地方是理解它在实际代码中的工作原理。有一个具体的例子，我不太明白......

def toChars(s):
    import string
    s = string.lower(s)
    ans = ''
    for c in s:
        if c in string.lowercase:
            ans = ans + c
    return ans

def isPal(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and isPal(s[1:-1])

def isPalindrome(s):
    """Returns True if s is a palindrome and False otherwise"""
    return isPal(toChars(s))

此代码应该检查字符串是否为回文。我对 isPal(s) 的工作原理有点迷茫。这是我正在阅读的步骤...

1. 判断s是否小于等于一个字符，如果是则返回True。
2. 如果 s 有多个字符，则从比较第一个和最后一个字符的表达式中返回一个 bool 值(True 或 False)。所以基本上检查第一个和最后一个字母是否相同。
3. 并返回函数再次运行的结果，并从字符串中删除第一个和最后一个字母。

令我困惑的是 return s[0] == s[-1] and isPal(s[1:-1]) 位。我不确定我是否理解基于第一个表达式返回 True/False 并返回函数的含义。老实说，我什至不确定返回函数的实际含义，我猜它只是再次运行该函数，但实际上并没有返回任何值。我也不明白这实际上如何判断字符串是否为回文。是不是一直打到return s[0] == s[-1] and isPal(s[1:-1])的第二部分，直到字符串，是否是回文或没有，减少到 1 个或 0 个字符？我唯一能想到的是 return s[0] == s[-1] 返回 false 值退出函数，返回 false？但我不觉得这实际上是 Python 的工作方式，至少在我的研究中到目前为止我还没有遇到任何说在函数中返回 False 会阻止 return 语句的第二部分执行，这将调用无论首尾字母是否相同，都会再次调用该函数。

此时我有点用头撞墙，所以任何见解都将不胜感激!

Answer 1

也许最好的方法是逐步处理让您感到困惑的那一行的值。

return s[0] == s[-1] and isPal(s[1:-1])

假设您要测试的字符串是“ABCDBA”，这是调用顺序

return s[0] == s[-1] and isPal(s[1:-1]) #evaluate to ("A" == "A" and isPal("BCDB")) - need to go deeper
return s[0] == s[-1] and isPal(s[1:-1]) #evaluate ("B" == "B" and isPal("CD")) - need to go deeper
return s[0] == s[-1] and isPal(s[1:-1]) #returns ("C" == "D")

请注意，在最后一行中，由于短路我们没有评估 isPal - 我们知道 False 和 X，其中 X 可以是 True 或 False 始终为 False。阅读更多相关信息 here .

在最后一行，我们深入到 isPal 中的 4 个函数。由于最后一行不需要我们再次评估 isPal()，我们开始“浮出水面”回到 isPal 的原始调用，它位于

def isPalindrome(s):
    """Returns True if s is a palindrome and False otherwise"""
    return isPal(toChars(s))