带有递归函数的回文检查，无需切片和循环

Question

我有一个作业，我必须制作一个 python 代码，使用返回布尔值的递归函数检查字符串是否为回文，但不允许使用反向切片或循环，也不允许更改函数格式，这是我的代码，但它一直返回 Truedef is_palindrome(s):    res = []    s = ['']    if len(s) < 2:        return True    else:        rev_s = is_palindrome(s[1:]) + s[0]        res.append(rev_s)        if res == s:            return True        return False

Answer 1

您可以检查给定字符串的第一个和最后一个字符是否相同，然后递归检查剩余的字符串是否为回文：

def is_palindrome(s):
    return len(s) < 2 or s[0] == s[-1] and is_palindrome(s[1:-1])

Answer 2

如果提到的函数签名def is_palindrome(s)是你老师给的签名，那么没问题，不需要传递任何额外的参数来实现目标。

你的老师（或者给你这个任务的老师很棒）只是想看看你是如何只用 1 个参数来处理这个问题的。

概念很简单，只需(to list with 3 values)在第二次递归调用中更改参数类型即可。

def is_palindrome(s):

    if type(s) is str:

        l = len(s) 

        if l == 0 or l == 1:

            return True

        else:

            return is_palindrome([s, 0, -1])

    else:

        string, start, end = s # s is list here

        if string[start] != string[end]:

            return False

        else:

            if(start + 1 >= end - 1):

                return True

            return is_palindrome([s, start + 1, end - 1])

def main():

    string1 = "abcba"

    string2 = "abcde"

    string3 = "AxxA"

    print(is_palindrome(string1)) # True

    print(is_palindrome(string2)) # False

    print(is_palindrome(string3)) # True

main();

以下内容不是您要查找的内容，但可能是您将来要查找的内容。

>>> def is_palindrome(s):

...     if s == "".join(reversed(s)):

...         return True

...     else:

...         return False

...

>>> is_palindrome("ABA")

True

>>>

>>> is_palindrome("ABC")

False

>>>

>>> is_palindrome("XXZZXX")

True

>>>

>>> is_palindrome("@#7")

False

>>>

>>> is_palindrome("1@#@1")

True

>>>

谢谢你。

Answer 3

我不确定这是否算作“更改函数格式”，但这是我对没有切片的递归版本的尝试：

def is_palindrome(s):

  def is_palindrome_r(i, j):

    if j <= i:

      return True

    if s[i] != s[j]:

      return False

    return is_palindrome_r(i + 1, j - 1)

  return is_palindrome_r(0, len(s) - 1)

内部函数is_palindrome_r是采用两个索引i和的递归函数j。最后一行在0（字符串的开头）和len(s) - 1（字符串的结尾）设置这两个索引的初始位置，并继续执行递归逻辑。递归函数有两个退出条件：

如果j <= i我们到达了回文的中心。如果我们已经走到这一步，我们知道所有其他字符对都匹配，我们不需要再进行任何比较。

如果两个角色的指向i和j 不匹配，这绝对不是一个回文，我们不需要做任何更多的比较。

否则我们还不知道序列是否完全回文，所以我们将索引向内移动一步 ( i + 1, j - 1) 并返回到步骤 1。