2

几个小时前，我观看了一段关于 Python 递归的视频，然后重新创建了视频中制作的程序，因此它可以在我的 Python 版本中运行。该代码有效，但有一点我不完全理解以及它在做什么。

def lower(s):
    s = s.lower()
    return s

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

def isPalindrome(s):
    if isPal(lower(s)) == True:
        print("{0} is a palindrome".format(s))

我遇到问题的部分是

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

我想知道的是为什么要返回它们，以及为什么是 s[1:-1] 而不是 s[0:-1] 如果您认为您知道任何有助于简化递归的好地方，请随意分享它们。提前致谢。

4

5 回答 5

5

为什么是 s[1:-1] 而不是 s[0:-1]

s[1:-1]返回s并切掉第一个和最后一个元素。仅切掉最后一个元素s[0:-1]返回。s

您需要切断两端以保留回文属性（如果它是回文），即与中间等距的元素是相同的。如果只砍掉一端，则移动中间，这将（在一般情况下）破坏该不变量。

这触及了自递归的核心：你做一件事，然后你委托一个具有相同属性的更简单的案例。

为什么返回 s[0] == s[-1] 和 isPal(s[1:-1])

之所以返回这是因为它首先检查第一个和最后一个元素是否具有回文属性（如上）并且下一个“层”也具有该属性。如果外对不相等，则不是回文，False将被返回；如果为真，则执行递归步骤，如果为真，则整个表达式返回True.

于 2013-09-19T15:15:27.667 回答
3

想象一下你有“皮划艇”这个词

如果：

'k' == 'k'如果是，程序将调用该函数：'aya'

然后程序将查看如果'a' == 'a'是，程序将调用该函数'y'

那么只有一个字母，所以程序返回True

于 2013-09-19T15:16:54.513 回答
3

这就是魔法发生的地方：

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

（我添加了括号，因此您对运算符的优先级非常清楚）。重要的是要知道 Python AND 语句将评估第一个参数，并且只有当它是True时，它才会评估第二个参数。如果第一个是False，那么它将False立即返回而不调用isPal()。这称为短路评估。Blender在他的帖子中做了一个很好的例子。

s[0]是字符串中的第一个字母，是字符串s[-1]中的最后一个字母。首先我们检查第一个和最后一个字母是否相同。如果它们不同，则字符串不可能是回文。如果它们相同，我们可以忽略它们并移动到字符串的内部。

s[1:-1]修剪掉第一个和最后一个字母，然后将其传递给isPal()函数，这恰好是我们当前所在的函数——这称为递归。当我们再次“递归”到函数中时，会创建一个新堆栈，创建新的局部变量，并且该函数的输入参数将与上一次调用中的不同。

我们继续检查第一个和最后一个字母，并一直递归到单词的中心。在这一点上，剩下 1 个或 0 个字符，如果我们已经走到那一步，我们就知道我们找到了一个回文。

当我们从这个最终的内部调用返回时isPal()，返回值（True如果已找到回文）被传递给调用函数，然后调用函数将其返回给它的调用函数，等等，直到最终的“外部”isPal()函数返回结果到初始调用者。我们将此过程称为“展开堆栈”。

这是一个例子：

s = 'racecar'
s[0] == s[-1] # True - both letters are 'r'
s = s[1:-1]   # s becomes 'aceca'
s[0] == s[-1] # True - both letters are 'a'
s = s[1:-1]   # s becomes 'cec'
s[0] == s[-1] # True - both letters are 'c'
s = s[1:-1]   # s becomes 'e'
len(s) <= 1   # This statement is now True, so the stack will start to unwind

从视觉上看，调用将如下所示：

'racecar' ---------
                  |
                  V    'aceca'
 True <--- isPal(   ) ----
             ^           |
        True |           V     'cec'
             ---- isPal(   ) ----
                    ^           |
               True |           V     'e'
                    ---- isPal(   ) ----
                           ^           |
                      True |           V
                           ---- isPal(   )  # We get all the way down here,
                                            # and then we start to return

在我们没有回文的情况下，会发生这种情况：

'race2car' --------
                  |
                  V    'ace2ca'
False <--- isPal(   ) ----
             ^           |
       False |           V     'ce2c'
             ---- isPal(   ) ----
                    ^           |
              False |           V     'e2'
                    ---- isPal(   ) ----
                           ^           |
                     False |           V
                           ---- isPal(   )  # Here the outer two letters
                                            # do not match, so we start to
                                            # return False
于 2013-09-19T15:24:33.900 回答
1

您正在检查第一个和最后一个s是否相同，因此一旦这样做，您将它们切掉并通过返回递归部分来检查下一个第一个和最后一个是否相同，并且它会不断将结果加在一起，直到有s 中 1 个或更少的字母。然后它会返回您到目前为止收集的内容并返回 True。

print(s)在 the 之前if len(s) <= 1:或print(s[0] == s[-1] and isPal(s[1:-1]))之后添加 aelse:可以帮助您更多地理解递归。

于 2013-09-19T15:11:52.723 回答
0

该步骤使用短路逻辑与，所以它的行为实际上是这样的：

if s[0] != s[-1]:
    return False
else:
    return isPal(s[1:-1])

至于s[1:-1]，您将第一个和最后一个字符与 进行比较s[0] != s[-1]，因此s[1:-1]只需删除第一个和最后一个字符并将结果字符串传递回isPal.

于 2013-09-19T15:13:06.030 回答