理解阶乘递归

Question

我在看递归的阶乘例子，想确认一下我理解得对不对！

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

我这样理解对吗：

阶乘(4) = 阶乘(4-1) * 4 = 阶乘(3-1) * 3 * 4 = 阶乘(2-1) * 2 * 3 * 4 = 阶乘(1-1) * 1 * 2 * 3 * 4 = 24

因为阶乘(1-1) = 阶乘(0)，而根据基本情况，阶乘(0) = 1，然后我们依次乘以 2、3 和 4。

这样理解对吗？

提前谢谢你！

Answer 1

是的，你描述的情况就是发生的事情。

需要注意的是，如果你给 n 输入一个不是整数的值，或者输入一个小于0的值，你的代码可能会陷入一个无限循环。

因此，建议在你的代码中加一个检查来避免这种情况：

if not isinstance(n, int): 
      return None

 elif n < 0: 
      return None

Answer 2

这可能会对你有帮助

(factorial 4)
(4 * (factorial 3))
(4 * (3 * (factorial 3)))
(4 * (3 * (2 * (factorial 1))))
(4 * (3 * (2 * 1)))
(4 * (3 * 2))
(4 * 6)
(24)

Answer 3

没错，这个是对的。不过因为这是递归，所以它的工作方式是相反的。我曾经有个面试官这样给我解释：

比如说，计算 fact(5)：

 - fact(5) = 5 * fact(4)
           - fact(4) = 4 * fact(3)
                     - fact(3) = 3 * fact(2)   
                               - fact(2) = 2 * fact(1)
                                         - fact(1) = 1 * fact(0) 
                                                   - fact(0) = 1
                                                   // This is where your condition returns 1.

现在，想象一下上面的 - 符号代表的是一个返回值。你基本上是返回 - 符号后面的内容。所以从最底下那一行开始，返回的是 1。接着，在 fact(1) 中，你就得到了 1，也就是 1 * 1。这个过程是以反向的方式进行的，像这样：

 = 120
 - fact(5) = 5 * 24
           - fact(4) = 4 * 6 = 24
                     - fact(3) = 3 * 2 = 6  
                               - fact(2) = 2 * 1 = 2
                                         - fact(1) = 1 * 1 = 1
                                                   - fact(0) = 1

记住，当你在处理递归时，所有的东西实际上都是反向工作的。这会帮助你更好地理解递归问题。

这也是为什么尾递归和相关的优化非常重要。在内存中，每一个调用都是被延迟的，直到上面的调用（在图中是下面的）完成并返回结果。所以，如果递归调用太深，就可能导致栈溢出，除非编译器或解释器通过将其转换成 OP 中的版本来进行优化，这样部分结果就能立即计算，而不是被延迟。Python 不进行这种优化，所以你在使用递归调用时要特别小心。