Python 递归阶乘函数

Question

找到此解决方案以在 python 中创建 factorial() 函数，但我无法理解 ' 为什么 ' 有效。

函数是：

def factorial(x):
  if x <= 1:
    return 1
   else:
    return x * factorial(x-1)

我无法理解 实际乘法发生在哪里？

在我看来，该函数会一直调用自身，直到它到达 1，并且 returns 1.有人可以启发我吗？我确定我错过了一些简单的东西。

Answer 1

`Where` 乘法发生：

    #        +-------------------------- HERE .MUL A, B  happens
    #        |                                     |  |
    #        |                                     v  v
    #        |                                     x  ( !(x-1) )
    #        v
    return x * factorial(x-1)
#              ---------( -1)
#              |            | <---------------           vvvvvvvvv
#                                             THIS sends recursive call
#                                                  to get B-value "down the line"
#                                                  while A is waiting to
#                                                          to receive B value
#                                                          needed for .MUL A, B
#                                                        B waits for return value
#                                                          from "recusive" call
#                                                          to the same function,
#                                                          but with off by one
#                                                          smaller number
#                                                  UNTIL  A == 2                | more exactly A { 2 | 1 |  0 }
#                                                         B == 1                |              B { 1 | 0 | -1 }
#                                                         for which case        | for which case
#                                                         factorial( 1 ) RETs 1 |   factorial( B ) RETs 1
#                                                         as a terminal state
#                                                         without any .MUL
#                                                         without any deeper
#                                                                     level
#                                                                     recursion
#                                                                     call
#                                                                     thus
#                                                                     "terminal"
#                                                                     state
# and since this moment, all "waiting" .MUL A, B-s start to get processed    
#                                                  from back to front
#                                                  one step after another
#                                                  1 * 2 * 3 * .. * A
#                                                  which is the definition of !A
# Q.E.D.

这是`why`有效

Answer 2

基本上每次调用 factorial(x) 都会创建堆栈框架，堆栈框架的层次结构是 formed.Every 调用等待下一次调用的答案，因此 on.Finally，当答案是主调用它收到了 returns 的答案。

栈帧是调用栈的一部分，每次调用子程序都会创建一个新的栈帧。因此，在我们上面的递归 Factorial 方法中，每次调用该方法时都会创建一个新的堆栈帧。堆栈帧用于存储一次例程调用的所有变量。所以，请记住，调用堆栈基本上就是一堆堆栈帧。

Answer 3

考虑几个简单的例子：

呼叫`factorial(1)`

这将立即return1

呼叫`factorial(2)`

x 在我们的第一个范围内是 2。
我们将进入else块
我们乘以 x，即 2 与 factorial(x-1)。 *x-1 是 1.
我们称之为 factorial(1) 这是我们的第一个案例。结果是 1.
我们return2

基本上就是这样，对于任何更高的数字，我们都会得到更多的范围，总是少调用阶乘，最终达到 1，我们终止并开始 return 返回值。

Answer 4

假设您调用 factorial(3)，它看起来是这样的。

阶乘(3):
return 3 * factorial(2) = ?
还不能 return 因为它没有值，请调用 factorial(2)

阶乘(2):
return 2 * factorial(1) = ?
还不能 return 因为它没有值，请调用 factorial(1)

阶乘(1):
return 1

现在冒泡了，因为 factorial(1) returns 1

factorial(2) = 2 * 1
returns 2

factorial(3) = 3 * 2
returns 6

运营结束

Answer 5

编程的一般技巧是插入 print 语句以帮助您了解代码运行时发生的情况。当您尝试修复损坏的代码时，这尤其有用，但也有助于理解新代码。在这种情况下，请尝试运行以下操作：

def factorial(x):
    print "x", x
    if x <= 1:
        print "base case, returning 1"
        return 1
    else:
        sub_fact = factorial(x-1)
        print "factorial(x-1)", sub_fact
        result = x * sub_fact
        print "return", result
        return result

factorial(4)

Answer 6

是的，0和1的阶乘是1，没有乘法，也没有下一个递归调用。

否则，你要注意，在我们与当前x相乘之前，我们必须得到下一个阶乘的结果。

因此，递归 "enters" 本身下降到停止条件（当 x==1 时），然后结果上升，如下所示：

factorial(5):
    (5 *(4 *(3 *(2 *(1*1)))))
- Read it from right to left, which is the order of recursive execution
- Note: (1*1) would not actually be executed because at x==1 recursion stops.

Because of multiplication rule (a*b = b*a) the direction is irrelevant (top to bottom or bottom to top).

Python 递归阶乘函数

Python recursive Factorial Function

python

factorial

Where 乘法发生：

这是why有效

呼叫factorial(1)

呼叫factorial(2)

`Where` 乘法发生：

这是`why`有效

呼叫`factorial(1)`

呼叫`factorial(2)`