难以理解递归

Question

我在这里做第一个递归练习：http://cscircles.cemc.uwaterloo.ca/16-recursion/

我按照明显的提示写了这个代码：

def countup(n):
  if n == 0:
    print('Blastoff!')
  else:
    countup(n - 1)
    print(n)

这个代码基本上是从0开始数到n（发射）。我就是不太明白它是怎么工作的——我看了可视化的效果，它从countup(n)走到countup(0)，然后打印出“发射”，一切都很好。之后，它似乎就停留在else循环里，开始打印之前的n值……为什么会这样呢？它是出于某种原因存储了n值吗？即使是这样，这段代码的机制到底是怎么运作的呢？任何帮助都非常感谢。谢谢！

Answer 1

考虑这个变体：

def countup(n):
  if n == 0:
    print('Blastoff!')
  else:
    print(n, end=', ')
    countup(n - 1)
       # print(n, end=', ')    reverse  

输出结果：

5, 4, 3, 2, 1, Blastoff!

与将打印顺序和递归调用反过来：

def countup(n):
  if n == 0:
    print('Blastoff!')
  else:
        # print(n, end=', ')    reverse  
    countup(n - 1)
    print(n, end=', ')

输出结果：

Blastoff!
1, 2, 3, 4, 5, 

你现在可以看到，当在 print(n, end=', ') 之前调用 countup(n - 1) 的递归时，函数必须一直走到最后的条件判断 if n == 0:，才会开始打印任何内容。

一旦满足了 if n == 0: 的条件，整个调用链就会被展开，按照相反的顺序打印出传给 countup 的参数。

再考虑一个经典的递归例子：反转一个字符串：

def rrev(s):
    if s == "":
        return s
    else:
        return rrev(s[1:]) + s[0] 

或者，更简洁地：

def rrev(s):
    return rrev(s[1:]) + s[0] if s else s

Answer 2

这个代码使用了递归来打印数字。
理解这个概念最好的办法就是看一个例子：

countup(3)
  countup(2)
    countup(1)
      countup(0)
        n == 0
        print('Blastoff!')
    print (1)
  print(2)
print(3)

每次这个函数被调用时，它会用 n-1 再次调用自己，直到 n==0。在这个时候，它就开始按照示例中的方式打印数字。

Answer 3

每次调用 countup() 函数时，它最终会回到最开始调用它的地方。接下来的那一行会打印出 n 的值，因为那是它在这次函数调用时的值。

每次你调用一个函数时，所有的变量名都是重新创建的，它们是 局部的。所以，每次你调用 countup()，你都有一个独立的 n 的值。

实际上，你是在创建一连串的 countup() 调用：

• 当你调用 countup(2) 时：n 的值是 2，不是 0，所以执行 else 的部分，接着调用 countup(1)

  • 当你调用 countup(1) 时：n 的值是 1，不是 0，所以执行 else 的部分，接着调用 countup(0)

    • 当你调用 countup(0) 时：n 的值是 0，打印 Blastoff!!，然后这个函数返回。

    
    countup(0) 调用返回后，接下来的那一行打印 n，在这次调用中仍然是 1。然后，函数返回。

  接着 countup(1) 调用返回，下一行打印 n，在这次调用中仍然是 2。然后，函数返回。