数字的阶乘，机器如何解释它？

Question

今天我在练习一些简单的数学问题，并且正在编写一个数字的阶乘，特别想了解一些东西。

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

x = int(input("Enter x : "))
y = fact(x)
print("{}! = {}".format (x,y))

这部分return n*fact (n-1) 在路上，我解释这个 n * fact 就像一个数字乘以事实，自己，然后放置 (n-1) 它会像 x = x * (x - 1) 但是如果我们用像 5 这样的数字来做这将是 5 = 5 * (5-1)。所以我不明白机器是如何走到 1 或 0 的。所以我在想，由于变量return，机器会一直往回走，直到它进入0。

有什么想法吗？

Answer 1

这称为递归。 "computer" 将其解释为堆栈的方式。

例如，考虑 fact(5)。计算机是这样解释它的：

push fact(5) to stack --> return 5 * fact(4), push fact(4) to stack
      where fact(4) --> 4 * fact(3), push fact(3) to stack
      where fact(3) --> 3 * fact(2), push fact(2) to stack
      where fact(2) --> 2 * fact(1), push fact(1) to stack
      where fact 1 --> 1 * fact(0), push fact(0) to stack
      where fact(0) --> 1. Pop from stack until empty.

因此，我们从 基本案例 开始构建，即 fact(0) = 1。因为我们知道 fact(1) 是 1 * fact(0)，fact(1) = 1。 fact(2) = 2 * fact(1), 所以 fact(2) = 2... fact(5) = 5 * 4 * 3 * 2 * 1 = 120.

Answer 2

On the way, I interpret this n * fact would be like a number multiplication by fact, by himself, and then placing (n-1)

您看到的是 recursion。定义说：

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.1 Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. At the opposite, recursion solves such recursive problems by using functions that call themselves from within their own code.

fact 是您程序中的一个函数（由 def 定义），它也 returns 在递归调用中使用了一些值。

递归函数必须遵守三个重要的法则：

递归算法必须有一个基本情况。（if (n==0) 在你的函数中）
递归算法必须改变其状态并向基本情况移动。（n - 1 在您的 n * fact(n - 1)
递归算法必须递归地调用自身。（fact(n - 1) 在你的函数中）

n 将乘以函数调用 fact(n - 1).
返回的数字

要查看幕后发生的事情，您可以使用 Python 中的 print 函数。

数字的阶乘，机器如何解释它？

Factorial of a number, How does the machine interpret it?

python

math

computer-science