Python递归和返回

Question

我是递归概念的新手，在我的编码经验中从未练习过这种魔法。我对 Python 递归感到非常困惑的是“return”的使用。更具体地说，我不太明白在某些情况下何时使用 return。我见过在递归之前使用 return 的情况，并且根本不需要 case return。例如：一个 Leetcode 问题：“给定二叉搜索树（BST）的根节点和一个值。您需要在 BST 中找到该节点的值等于给定值的节点。返回以该节点为根的子树。如果这样的节点不存在，你应该返回NULL。”# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def searchBST(self, root, val):        """        :type root: TreeNode        :type val: int        :rtype: TreeNode        """        if root == None:            return root        if root.val == val:            return root        elif root.val > val:           return self.searchBST(root.left,val)        else:           return self.searchBST(root.right,val)为什么我需要返回“self.searchBST(root.left,val)”和“self.searchBST(root.right,val)”？如果这两行都没有加return，程序是不是还要递归运行，直到满足root.val == val或者root== None的条件，并返回一个值？（我知道在实践中并非如此，我只是想将其概念化）。此外，有人可以向我展示在递归中使用 return 的一般准则吗？先感谢您！

Answer 1

如果你只写：

self.searchBST(root.left,val)

代替

return self.searchBST(root.left,val)

它将执行递归搜索，但不会将结果返回到调用它的块。当它达到您想要的值（或找不到）时，该调用将执行

return root

但是之前的调用只会丢弃这个值，而不是把它返回到递归链中。

Answer 2

让我们举一个更简单的例子，您也可以将相同的逻辑应用于您的方法，

def fact(n):

    #Base case

    if n in [0, 1]:

        return 1

    #Recursion. Eg: when n is 2, this would eventually become 2 * 1 and would be returning 2 to the caller

    return n * fact(n-1)

一般来说，递归函数有两种情况，一种是基本情况，另一种是对自身的递归调用。请记住，这是一个函数，理想情况下应该向调用者返回一些东西。这就是return需要声明的地方。否则，您将不会向调用者返回正确的值。

如果这两行都没有加return，程序是不是还要递归运行，直到满足root.val == val或者root== None的条件，并返回一个值

返回值是。但它会返回到之前的调用（等等），因此它会返回到self.searchBST(root.left,val)or之一self.searchBST(root.right,val)。您仍然需要从该点返回到函数的调用者。因此，您需要拥有return self.searchBST(root.left,val)or return self.searchBST(root.right,val)。

Answer 3

语句退出当前正在运行的return函数并返回一个返回值，然后可以像 Python 中的任何其他值一样使用该值：分配给变量，作为参数传递给另一个函数，或者...作为调用的返回值返回功能。

def some_func():

    return 'result'

x = some_func()  # after this, x == 'result'

如果你在没有捕获返回值的情况下调用一个函数，它就会丢失。因此，如果您只调用some_func()，它将被执行。

some_func()  # this works, but 'result' is lost

调用另一个函数的函数也是如此，即使那个函数本身就是：

def some_other_func1():

    x = some_func()

    return x

def some_other_func2():

    return some_func()  # exact same result as some_other_func1()

def some_recursive_func(n):

    if n == 0:

        print('Reached the end')

        return n

    else:

        print(f'At {n}, going down')

        return some_recursive_func(n-1)

print(some_recursive_func(3))  # prints a bunch of lines, but always prints `0` at the  end