如何用Python递归找到回文？

Question

我刚开始探索编程的奇妙世界。现在我想写一段代码来识别数字回文。这里我只关注数字，不考虑文本。我想学习如何使用递归，但我就是搞不明白，感觉卡住了，不知道哪里出错了。

我的想法是先比较字符串的第一个字符和最后一个字符，如果它们相同，就把这两个字符删掉，然后再重复这个过程。最终要么什么都剩不下（这说明它是个回文），要么会剩下几个不匹配的字符（这说明不是回文）。

我知道还有更好的方法来找回文，但我只是想试试递归这个概念。

那么，问题出在哪里呢？

def f(n):
    global li   
    li=list(str(n))
    if (len(li)==(1 or 0)):
        return True
    elif li[len(li)-1]==li[0]:
        del li[0]
        del li[len(li)-1]
        if len(li)==0:
            return True
        if len(li)>0:
            global x
            x=''.join(li)
            str(x)
            f(x)
    else:
      return False

提前谢谢你们！

Answer 1

你的解决方案有几个问题。让我逐行分析一下。

1. 如果你不打算在函数外部修改变量，就不需要使用global语句。因此，我把你代码中两行global的部分删掉了。

2. li=list(str(n))：把字符串转换成列表其实没必要，因为在Python中，字符串的用法和不可变列表很像。所以直接用li = str(n)就可以了。

3. if (len(li)==(1 or 0)):：虽然看起来没问题，但这实际上是比较值的错误方式。or运算符会返回第一个“真”的值，所以在这个情况下，它总是返回1。你可以用in运算符来检查左边的值是否在右边的值中。如果把右边的值写成元组(1, 0)，就没问题了。此外，if语句的括号也不需要。你应该写成：if len(li) in (1, 0):

4. elif li[len(li)-1]==li[0]:是可以的，但在Python中我们可以更简洁地写，因为它支持负数索引：elif li[-1] == li[0]:

5. 由于我们在第2点中不使用列表（可变序列），所以不能对它们使用del li[0]。而且，在Python中，删除列表的第一个元素效率很低（整个列表必须被复制）。同样的原因，我们也不能使用del li[len(li)-1]。相反，我们可以用“切片”操作符来提取字符串的子串：li = li[1:-1]

6. if len(li)==0:这个判断写得太长了。在Python中，空字符串和空列表在if中测试时会被视为False。所以你可以写成if not li:

7. if len(li)>0:：你不需要再次检查li是否不为空——你在第6点已经检查过了。所以简单用else:就可以了。或者更好的是，直接把这一行删掉，把后面的代码缩进，因为第6点的if里面已经有return了。如果没有进入if，那我们自然就在else里了。

8. x=''.join(li)：我们不需要把字符串再转换成字符串，因为在第2点的决定已经不需要了。把这一行删掉。

9. str(x)：这一行在你的代码中没有任何用处，因为str()不会就地修改它的参数，而是返回一个新值（所以x = str(x)才有意义）。你也可以把它删掉。

10. f(x)：这是在Python中调用递归函数的有效方式，但你得对它的返回值做点什么。也许返回它？我们可以改成：return f(li)（因为我们不再有x这个变量了）。

最后我们得到以下代码：

def f(n):
    li = str(n)
    if len(li) in (1, 0):
        return True
    elif li[-1] == li[0]:
        li = li[1:-1]
        if not li:
            return True
        return f(li)
    else:
        return False

这几乎是我们需要的，但还有一点可以改进。如果你看看if not li: return True这一行，你会发现它们其实是多余的。如果我们删掉它们，f会用空字符串作为参数被调用，len(li)会等于0，True也会被返回。所以我们就把这些行删掉：

def f(n):
    li = str(n)
    if len(li) in (1, 0):
        return True
    elif li[-1] == li[0]:
        li = li[1:-1]
        return f(li)
    else:
        return False

就这样！祝你成为一名成功的程序员好运！

Answer 2

在深入研究之前，if (len(li)==(1 or 0)): 这个写法并不会像你想的那样工作。(1 or 0) 这个表达式总是会被计算为 1。

你可能想要的是：

if len(li) in (1, 0):

Answer 3

几点建议

• 为什么 x 和 li 是全局变量？在递归中，所有的变量应该是局部的。
• 为什么要在 str 和 list 之间来回转换？它们都可以用下标访问，没必要这样做。
• 你需要返回递归调用的结果： return f(x)

试试这些建议，看看效果如何。