Python 递归返回 None 类型

Question

我不太明白，怎么才能返回一个 List 而不是 None 呢？

class foo():
    def recursion(aList):
        if isGoal(aList[-1]):
            return aList
        for item in anotherList:
            newList = list(aList)
            newList.append(item)
            recursion(newList)

    someList = [0]
    return recursion(someList)

简单来说，这段代码是用来记录所有的路径（从0开始）。谁先到达100，就会被返回。isGoal() 是用来检查路径的最后一个数字是不是100。而 anotherList 是一个包含随机数字的小列表（范围从0到100）。

Answer 1

这个函数是这样的：

def recursion(aList):
    if isGoal(aList[-1]):
        return aList
    for item in anotherList():
        newList = list(aList)
        newList.append(item)
        recursion(newList) # here you ignore what recursion returns
    # when execution reaches this point, nothing is returned

如果执行到我加的注释时，说明for循环已经完成，函数就会结束，并且什么都不会返回。当你退出一个函数而没有执行return语句时，默认会返回None。你必须确保在递归函数中返回一些东西。

我不能建议你怎么重写这个函数，因为我不知道它的目的是什么。对我来说，它需要怎么改并不明显。不过，我可以非常肯定地说，你必须返回一些东西！

Answer 2

return 语句

当我刚开始学习递归的时候，这个问题让我花了不少时间才弄明白。

在使用 Python 的函数或方法时，有一点要记住，那就是它们总是会返回一个值。也就是说，如果你在函数的主体中忘记写 return 语句，Python 会自动帮你处理，最后会返回 None。

这意味着，如果你在函数内部搞错了，把 return 放错地方或者干脆不写，那么你本来期待的返回值，使用 print type(messed_up_function()) 时就会显示 NoneType。

递归修复

考虑到这一点，在处理递归时，首先要确保你有一个基本情况，除了归纳情况，也就是要防止出现无限递归循环。

接下来，确保在这两种情况下都有返回值，像这样：

def recur(val):
    """
    takes a string
    returns it back-to-front
    """
    assert type(val) == str
    # the base case
    if len(val) == 1:
        return val
    # the inductive case
    else:
        return val[-1] + recur(val[:-1]) # reverses a string char by char

这样做的好处是它总是会 return，并且完全防止无限递归，因为它有一个有效的基本情况，并且在每一步归纳中长度都会减少。

堆栈查看器来调试递归函数

如果我们在基本情况的开头加上 assert False，然后运行 recur('big')，我们会得到这样的堆栈结构：

从中我们可以看到，在每一步递归中，val 这个函数的唯一参数会越来越小，直到它达到 len(val) == 1，然后就会到达最终的返回值，或者在这个例子中是 assert False。所以这是一个很方便的方式来调试你的递归函数或方法。在 IDLE 中，你可以通过在命令行中调用 Debug > Stack Viewer 来访问这样的视图。