23

I'm wondering how to break out of a recursive loop to the main function. I am trying to do a simple palindrome exercise. The function should return True for "redivider" but the return True is being passed to is_pal() and the function isn't breaking. Short of adding a second variable to is_pal to track True/False, what is the proper way to break out of this recursive loop?

def first(word):
    return word[0]

def last(word):
    return word[-1]

def middle(word):
    return word[1:-1]

def is_pal(str):    
    if len(str) == 1: 
        return True

    if first(str) == last(str) and len(str) > 1: 
        is_pal(middle(str))
        
print is_pal("redivider")
4

6 回答 6

19 
def is_pal(str):    
    if len(str) <= 1: 
        return True

    if first(str) == last(str): 
        return is_pal(middle(str))
    else:
        return False

这样，如果它们不匹配，False则返回；如果它一直到最后，则返回 True。我还消除了冗余条件并检查了偶数长度回文的边缘情况。

于 2012-05-11T02:18:20.863 回答
17

你不会“打破”递归函数。试图这样做表明你以错误的方式思考他们。目前你的递归调用忽略了输出，这意味着递归是没有意义的；无论is_pal(middle(str))返回什么都对函数的返回值没有影响。

递归算法通过将问题分解为较小的问题来解决输入问题，递归地得到较小问题的解决方案，然后使用较小的解决方案构造较大问题的正确解决方案。您不会“打破”内部调用，而是将解决方案返回到一个级别。您不知道（或需要知道）您是处于内部呼叫还是顶级呼叫中。在任何一种情况下，你的函数都应该做同样的事情：True如果参数是回文，False则返回，否则返回。

您尝试实现的算法基本上是这样的：

  1. 如果字符串长度为 1，则为回文（return True）
  2. 否则，如果第一个字符与最后一个字符相同，则如果中间字符是回文，则输入是回文。

所以这意味着一旦你确定第一个和最后一个字符是相同的，“我的输入是回文”的答案与“中间字符是回文”的答案完全相同。您需要返回该答案以履行您的合同。所以递归调用应该return is_pal(middle(str))不仅仅是is_pal(middle(str)). 如果这是一个顶级电话，那就是答案；如果这不是顶级调用，那么外部调用将需要这个答案来解决外部问题的答案（在这种情况下，只需返回它）。

顺便说一句，您的算法还有其他一些问题。

  1. 你永远不会 return False，所以答案永远不会是False（在这种情况下，如果第一个和最后一个字符不匹配，你碰巧None从函数的末尾掉下来意外返回，并且在大多数情况下None可能会代替False，但它仍然不是真的正确）。

  2. 如果字符串的长度是0而不是 1（如果传入一个空字符串，或者如果传入一个偶数长度的回文，一旦所有相等的第一个和最后一个字符对被剥离，就会发生这种情况），那么你不返回正确答案，实际上你试图获取空字符串的第一个和最后一个字符，这会导致异常。

于 2012-05-11T02:31:08.640 回答
17

在 Python 中打破递归函数的一种方法是抛出异常并在顶层捕获它。有人会说这不是思考递归的正确方法，但它可以完成工作。此外，如果任务是识别数组/数组数组/ndarray 等中的“问题”元素，则中断技术很方便，因为它会在识别出全局解决方案后阻止算法继续进行。

def solve_problem(lst):
    def solve_rec(l):
        '''has impl. that may throw an exception '''
    try:
        solve_rec(lst)
        return True
    except:
        return False
于 2018-03-26T15:18:21.070 回答
2

exit()您可以在使用该功能打印结果后退出程序。

这可能不是一个好的做法，但它可能是您正在寻找的。

于 2019-07-07T07:43:30.703 回答
0

你错过了回报。另外，不要str用作变量名。最后一件事，第一个和最后一个函数可以命名得更好一些。

def first_letter(word):
    return word[0]

def last_letter(word):
    return word[-1]

def middle(word):
    return word[1:-1]

def is_pal(word):    
    if len(word) == 1: 
        return True

    if first_letter(word) == last_letter(word) and len(word) > 1:
        return is_pal(middle(word))

print is_pal("redivider")
于 2012-05-11T02:17:19.613 回答
0

您需要返回 False 以防它们不匹配并添加返回语句。此外，您可能需要检查 len(str)==0 和 len(str)==1：

def is_pal(str):
    if len(str) in [0, 1]:
        return True
    if first(str) == last(str) and len(str) > 1:
        return is_pal(middle(str))
    else :
        return False
于 2012-05-11T02:18:32.737 回答