理解阶乘递归

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)，根据基本情况，结果为1，然后我们乘以2，再乘以3，最后乘以4。

这是正确的看法吗？

提前致谢！

- heather

---

这确实是正确的思考方式。 - chrk

正确的递归方式，但您假设乘法是可交换的。应该是4*3*2*1*factorial(1-1)或者甚至是4*(3*(2*(1*factorial(1-1))))。 - ypercubeᵀᴹ

Answer 1

是的，它就是递归。但由于它是递归，所以它的工作方式与正常函数相反。我曾经有一位面试官这样向我解释：

比如说，对于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。然后，实际上返回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

记住，当你在处理递归时，一切都是反过来的。这对于分解任何递归问题应该非常有帮助。

这也是为什么尾递归及其相关优化如此重要的原因。在内存中，每个调用都会被延迟执行，并且不能返回，直到它上面的调用（在图示中下方）完成并返回。因此，非常深的递归调用可能会导致堆栈溢出，除非编译器/解释器通过将其转换为原始版本来优化此问题，从而立即计算部分结果而不是延迟。Python不执行此优化，因此您必须小心使用递归调用。

- gran_profaci

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)

- lifeisbeautiful

Answer 3

是的，你所描述的就是正在发生的事情。

需要注意的一点是，如果您为n输入非整数值或小于0的n值，则看起来您将陷入无限循环。

在您的代码中添加一个检查可能是值得的：

if not isinstance(n, int): 
      return None

 elif n < 0: 
      return None

- Pash101