Python: 递归检查字符串是否为回文字符串

Question

我的任务是定义一个过程is_palindrome, 以字符串作为输入并返回一个布尔值来指示输入的字符串是否是回文。在这种情况下，单个字母应返回True，空字符串''也应如此。

不幸的是，我没有得到预期的结果。感谢帮助。

我的代码版本1:

def is_palindrome(s):
    if s == '':
        return True
    else:
        if (ord(s[0]) - ord(s[len(s)-1])) == 0:
            is_palindrome(s[1:len(s)-1])
        else:
            return False

print is_palindrome('')
#>>> True    (expected = True)

print is_palindrome('abab')
#>>> False    (expected = False)

print is_palindrome('abba')
#>>> None    (expected = True)

print is_palindrome('andrea')
#>>> None    (expected = False)

print is_palindrome('abaaba')
#>>> None    (expected = True)

我通过调试器追踪了我的代码，似乎逻辑是正确的，因为代码按照适当的路径执行。然而，最终结果似乎在某些情况下会切换到“无”状态，如上所述。

如果我将代码更改为以下内容：

我的代码版本2：

def is_palindrome(s):
        if s == '':
            result = True
        else:
            if (ord(s[0]) - ord(s[len(s)-1])) == 0:
                is_palindrome(s[1:len(s)-1])
            else:
                result = False
        return result

print is_palindrome('')
#>>> True    (expected = True)

print is_palindrome('abab')
#>>> False    (expected = False)

print is_palindrome('abba')
#>>> Error    (expected = True)
UnboundLocalError: local variable 'result' referenced before assignment 

print is_palindrome('andrea')
#>>> Error   (expected = False)         
UnboundLocalError: local variable 'result' referenced before assignment

print is_palindrome('abaaba')
#>>> Error    (expected = True)
UnboundLocalError: local variable 'result' referenced before assignment

- codingknob

---

在if语句中尝试使用result = is_palindrome(s[1:len(s)-1]) - Joran Beasley

如果这是作业，请将其标记为作业。 - Ned Batchelder

这很奇怪：(ord(s[0]) - ord(s[len(s)-1])) == 0。 s[0] == s[-1] 行不行？ - Ned Batchelder

同样地，s == "".join(reversed(s)) 也可以用来判断一个回文。 - Joran Beasley

@JoranBeasley：好吧，如果我们这样做，为什么不用s == s [:: -1]？假设OP有递归要求。[PS：单字母情况有效，因为s [0] == s [len（s）-1] == s [1-1] == s [0]]。 - DSM

Answer 1

在你的第一个例子中，你忘记了一个返回语句：

def is_palindrome(s):
    if s == '':
        return True
    else:
        if (ord(s[0]) - ord(s[len(s)-1])) == 0:
            # v-- forgot this here
            return is_palindrome(s[1:len(s)-1])
        else:
            return False

- mVChr

---

谢谢您指出我的疏忽。哎呀！非常感谢您。我已经按照Ned Batchelder的建议进行了更改。 - codingknob

还要注意许多回答者使用的速记法。s[1:len(s)-1]更简洁地写作s[1:-1]。我认为这主要适用于简洁的代码，但如果您喜欢使用len()，最好在函数开头只调用一次并重复使用结果。我相信mVChr已经知道所有这些，但由于OP是Python的新手，所以我认为值得额外注意。 - ely

@EMS - 我同意你的观点，感谢你提醒我。我是 Python 的新手。 :-) - codingknob

Answer 2

        is_palindrome(s[1:len(s)-1])

需要...

        return is_palindrome(s[1:len(s)-1])

在你的第一个版本中，或者

        result = is_palindrome(s[1:len(s)-1])

否则，你实际上从未将递归调用的返回值传播回原始调用者。

- Amber

Answer 3

# ask user to enter any string
a = raw_input("Enter the string : ")
#palindrome check
print (a == a[::-1]) and "String is palindrome" or "String is not palindrome"

- Swamy

Answer 4

def is_palindrome(s):
    if not s:
        return True
    else:
        return s[0]==s[-1] and is_palindrome(s[1:-1])

或者，如果你想要一个一行的代码：

def is_palindrome(s):
    return (not s) or (s[0]==s[-1] and is_palindrome(s[1:-1]))

希望这有所帮助。

- inspectorG4dget

---

有人能解释一下为什么当输入是单个字符时，Python索引应该在单行代码中正确工作的直觉吗？我已经测试过了，它确实可以工作，但是'a'[1:-1]返回空字符串的想法很奇怪。如果'a'[1]会出错，那么'a'[1:-1]也应该出错吧？这对我来说似乎不太符合Python的风格。似乎对于任何K > len(list)，list[K:-1]都会返回''。奇怪；我认为我更喜欢一个索引错误。 - ely

@EMS：这是因为尽管索引1不存在，'a'[1:]为空，正如预期的那样。对于L=[1,2,3,4]，L[7:]是[]，这是直观的。这解释清楚了吗？ - inspectorG4dget

顺便提一下，对于数值编程来说，这种空列表惯例并不是期望的行为。当索引超出对象范围时不抛出错误是一件坏事。我实际上非常惊讶NumPy的创造者没有为他们的ndarrays更改这个行为。 - ely

这是一个非常好的问题。我需要思考一下。如果 L[7] 是 None，那么程序员会认为“啊！这里有东西，这意味着我可以给它赋值”<- 这是错误的。因为为了这样做，Python 必须用 None 来“填补空白”，浪费内存。此外，这与 [None]*8 没有任何区别，这将导致令人讨厌的软件设计错误。 - inspectorG4dget

L[7] 返回 [] 意味着在 L 的第 7 个索引处存在一个空列表。你仍然在用 C 的术语思考这个问题。Python 列表不需要是同质的，所以这也会成为一个问题。 - inspectorG4dget

Answer 5

让我们逐行分析您的第二个示例：

def is_palindrome(s):

在这种情况下，我们让 s = "abba"，这是您遇到错误的第一个字符串：

        if s == '':

被评估为

        if 'abba' == '':

这里的条件是False，因此我们直接跳到else部分：

        else:
            if (ord(s[0]) - ord(s[len(s)-1])) == 0:

这个if语句等同于：

            if (97 - 97) == 0:

它是True，所以递归发生：

                is_palindrome(s[1:len(s)-1])

或者

                is_palindrome('bb')

现在无论递归的结果是什么，我们都忽略它，因为返回值没有被保存。因此，当我们到达这一行时：

        return result

我们从未定义过result，因此Python会出现错误。

其他帖子已经很好地回答了你的问题。我发布这篇文章是为了展示追踪程序以查找/修复错误的重要性。

- Joel Cornett

---

Joel非常感谢您演示了如何跟踪我的函数。在我写作和学习的过程中，我会将这个技巧融入到我的实践中去。 - codingknob

Answer 6

Java的回应

public class Varios {

/**
 * @param args the command line arguments
 */
  public static void main(String[] args) {
    System.out.println( pali("anitalavalatina"));
  }
  static boolean pali(String palabra){
    System.out.println(palabra);
    if (palabra.length()-1<2) 
            return true;
    if(palabra.charAt(0)!=palabra.charAt(palabra.length()-1)) return false;
    return pali(palabra.substring(1,palabra.length()-1));
  }

}

- edicson pineda