python - return 函数在递归中是如何工作的？

Question

我不明白 return 语句在任何递归函数中是如何工作的（在 python 中）。当您在递归函数中返回“东西”时，有人可以给我一些关于发生了什么的基本示例吗？

Answer 1

递归是一种优雅的编程风格，其中函数以更简单的形式调用自身，直到实现最简单的形式。

这种最简单的形式称为“基本情况”（在下面的示例中，基本情况是if n == 1: return 1因为对于阶乘，1 是您需要达到的最简单情况），这是一个测试以查看输入是否是最简单的可能状态。

递归函数的另一部分是“递归情况”，它进一步简化了函数（在下面的示例中，n * factorial(n-1)是递归情况，因为它使用 来简化函数n-1）。

一个简单的递归阶乘函数：

def factorial(n): # only works for positive numbers
    if n == 1: return 1 # base case
    return n * factorial(n-1) # recursive case; only executed if the above is not
                              # executed because 'return' stops a function

阶乘是直到并包括所有数字的乘积n。

让我们把它分开 factorial(4)：：

1. 是n1？不，所以return n * factorial(n-1)
2. 4 * factorial(4-1)=4 * factorial(3)
3. 是n1？不，所以return n * factorial(n-1)
4. 3 * factorial(3-1)=3 * factorial(2)
5. 是n1？不，所以return n * factorial(n-1)
6. 2 * factorial(2-1)=2 * factorial(1)
7. 是n1？是的，所以return 1

现在让我们跟踪调用：

步骤 1、3、5 只是检查，所以它们并没有真正返回任何东西：

• 第2步：factorial(4) = 4 * factorial(3)
• 第4步：factorial(3) = 3 * factorial(2)
• 第 6 步：factorial(2) = 2 * factorial(1)
• 第 7 步：factorial(1) = 1。

因此，跟踪return语句：1 * 2 * 3 * 4 = 24，这是 4 的阶乘。

Answer 2

当一个函数进行递归调用时，控制权传递给被调用的函数。当一个函数返回时，控制权从那个函数传递给调用它的那个函数。这就是交互式调试器描述正在发生的事情的方式：步入函数，步过每个语句，步出函数。

函数调用的常用簿记是称为堆栈的结构。我们应该想象一堆放在弹簧上的盘子。函数的每次调用（调用）都是一个“推”到堆栈“顶部”的板。函数的每次返回都会从堆栈中“弹出”该调用。

Answer 3

这是一个使用缩进来表示递归调用的简单示例（通过测量堆栈的深度）

>>> import inspect
>>> def factorial(n):
...     print('{:{}}factorial({})'.format('', len(inspect.stack()), n))
...     retval = 1 if n == 1 else n * factorial(n-1)
...     print('{:{}}return {}'.format('', len(inspect.stack()), retval))
...     return retval
... 
>>> factorial(5)
  factorial(5)
   factorial(4)
    factorial(3)
     factorial(2)
      factorial(1)
      return 1
     return 2
    return 6
   return 24
  return 120
120