了解阶乘递归 [英] Understanding factorial recursion

问题描述

我正在查看递归的阶乘示例，只是想确保我正确理解了它！

I'm looking over the factorial example of recursion and would just like to make sure that I'm understanding it correctly!

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

factorial(4) = factorial(4-1) * 4 = factorial(3-1) *3 *4 = factorial(2-1) *2 *3 *4 = factorial(1-1) *1 *2 *3 *4 = 24

因为阶乘(1-1)=阶乘(0)(根据基本情况显示= 1，然后我们乘以2，然后乘以3，然后乘以4.)

because factorial(1-1) = factorial(0) which as the base case shows = 1 and then we multiply by 2, then 3 then 4.

这是正确的观看方式吗?

Is that the correct way of looking at it?

提前谢谢！

推荐答案

是的.但是由于它是递归的，所以它的工作方式相反.我曾经有一个面试官这样向我解释:

Yes it is. But since it's recursion, it works the opposite way. I once had an interviewer explain it to me like this :

对事实(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级联中，例如:

Now, imagine that the - sign above stands for a return. You basically return whatever is after the - sign. So from the lowest line, 1 is returned. Then, you have 1 returned in fact(1) i.e. 1 * 1. So it happens in a REVERSE cascade like :

 = 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

请记住，每当您进行递归操作时，一切实际上都是相反的.这确实可以帮助您解决所有递归问题.

Remember that whenever you work on recursion, everything actually works in reverse. That should really help you breaking any recursion problem down.

这实际上就是为什么尾递归和相关优化如此重要的原因.在内存中，这些调用中的每一个都被延迟，并且直到其上方的调用(在图下方)结束并返回之前，无法返回.因此，除非编译器/解释器通过将其转换为OP中的版本来对其进行优化，否则非常深的递归调用可能会导致堆栈溢出，从而立即对部分结果进行求值，而不会延迟. Python不会执行此优化，因此您必须谨慎对待递归调用.

This is actually why tail recursion and the related optimization are so important. In memory, each of those calls is delayed and can't return until the calls above it (below in the diagram) finish and return. So a very deep recursive call can cause a stack overflow unless the compiler/interpreter optimize this by turning it into the version in the OP, such that the partial results are evaluated immediately and not delayed. Python does not perform this optimization and so you must be careful with your recursive calls.

这篇关于了解阶乘递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！