理解阶乘递归

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.

这是看待它的正确方法吗？

提前致谢!

Answer 1

是的.但由于它是递归,它的工作方式正好相反.我曾经有一位面试官这样向我解释:

说,事实上(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*1.所以它发生在REVERSE级联中,如:

 = 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不执行此优化,因此您必须小心递归调用.