另一个被递归弄糊涂的编码器

Question

假设我想将两个数字相加，但我只能递增和递减 1。我可以通过多种方法解决这个问题，包括使用递归。当我添加 m 和 n 时，我可以使用以下 Python 定义：

def slowAdd(m, n):
    if n == 0:
       return m
    else:
       return 1 + slowAdd(m, n-1)

这对我来说真的很困惑。有人能解释一下最终的返回调用是如何运作的吗？将定义的函数的值加到 1 时，Python 如何解释它？

Answer 1

好吧，让我们看一个超级简单的函数。

def super_simple_function():
  return 0

当我这样做时会发生什么x = super_simple_function()？

>>> x = super_simple_function()
>>> x
0

那是因为函数的返回值为零。所以有一个函数对象，它在调用时给（返回）一个值。

让我们一行一行地看看你的递归函数。试想一下，我们在第2和3作为我们的参数传递，就像这样：slowAdd(2, 3)。

第 1 行：def slowAdd(m, n)
这意味着第一个参数等于m和第二个，n。因此，在我们的例子中，m = 2和n = 3。

第 2 行：if n == 0
这是在 时触发的条件n equals to 0。好吧，现在n = 3这个条件被忽略了。

第 3 行：return m
由于n不等于 0，因此暂时忽略此行；我们会回来的。

第 4 行和第 5 行：else: return 1 + slowAdd(m, n-1)
这里发生了三件事。

1. 我们收到 的返回值slowAdd(m, n-1)。
2. 我们给返回值加 1
3. 我们返回 #2 的总和。

由于#1，这个函数被称为递归。可以想象，这个函数会一直调用自己直到n == 0，此时它返回m而不是1 + slowAdd(m, n-1)。因为我们n在每次递归中都递减1，所以我们肯定知道n最终会等于 0。

所以这基本上就是当我们(2, 3)作为参数传递时函数正在做的事情：

1st recursion: return 1 + slowAdd(2, 2)
2nd recursion: return 1 + slowAdd(2, 1)
3rd recursion: return 1 + slowAdd(2,0)
4th recursion: return 2            # n is finally 0!

其中加起来2 + 1 + 1 + 1 = 5。