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 = None

class 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 xdef 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