使用递归检查回文
提问于 2016-05-06 22:36:10
我使用了以下代码来检查字符串是否为回文。但是，当字符串是回文时，它将返回None。
def check(a):
if len(a)==1 or len(a)==0:
return True
if a[0]==a[len(a)-1]:
check(a[1:len(a)-1])
else:
return False
print check("radar")
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-05-07 23:19:34
您需要在函数中返回递归的结果：
def check(a):
# Base Case
if len(a) < 2:
return True
# Recursive Call
if a[0] == a[-1]:
check(a[1:-1])
else:
return False
return check(a[1:-1])
print check("radar")奖金信息
函数在检查字符串a时执行重复工作。为了避免重复的函数调用，并大大提高算法的性能，您可以考虑回忆录。否则，您可以构建一个大型调用堆栈，并可能导致stack overflow error (嘿，这是网站的名称.)。
下面是实现回忆录的一种可能的方法，方法是围绕您的函数构建一个类：
class check:
def __init__(self):
self.memo = {}
def Check(self, a):
# Base Case
if len(a) < 2:
return True
# Check Memo
if a in self.memo:
return self.memo[a]
# Recursive Call
if a[0] == a[-1]:
self.Check(a[1:-1])
else:
return False
# Memoize
self.memo[a] = True
return self.Check(a[1:-1])
print check().Check("rats live on no evil star")页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37085343
复制
腾讯云开发者
