使用递归方法调用的阶乘计算

本文关键字：阶乘 计算 调用 递归方法 | 更新日期: 2023-09-27 18:33:20

这段代码来自书："C# 5.0 in a Nutshell"，是LinqPad上的示例。 在第39页，它说：

"这种方法是递归的，这意味着它调用自己。每次输入方法时，在堆栈上分配一个新的 int，每次方法退出时，int 是已解除分配。

使用字面上的 5 个结果和答案 120(3 个生成 6(

有人可以解释一下这是如何工作的吗？我是一名 VB 程序员，试图学习 C#，并希望了解这样的结构。我已经单步执行了很多次，无法理解返回 x == 0 和 1 后会发生什么。 在x等于零之前，执行流程很容易理解。 之后，最后一个 return 语句似乎被重复执行(神奇地(，直到x递增回其原始值，然后返回到最初调用的位置并产生上述(神奇的(数字结果。

static void Main()
{
    Console.WriteLine (Factorial(5));
}
static int Factorial (int x)
{
    if (x == 0) return 1;
    return x * Factorial (x-1);
}

使用递归方法调用的阶乘计算

Call Factorial(3) (which returns 3 * 2)
  x doesn't == 0
  return 3 * Factorial(2)  
             Calls Factorial(2) (which returns 2 * 1)
               x doesn't == 0
               return 2 * Factorial(1)  
                          Calls Factorial(1) (which returns 1 * 1)
                            x doesn't == 0
                            return 1 * Factorial(0)
                                       Calls Factorial(0) (which returns 1)
                                         x == 0 so return 1

重要的一点是递归函数必须具有终止条件，否则它将无限调用自己(直到它耗尽堆栈空间(。在您的示例中，if (x == 0) return 1;是终止条件。由于函数调用自身的参数值比调用时少 1，因此最终它将以 0 调用自身，这就是递归结束的时候。

不过，这带来了此代码的问题。如果您使用负数调用，它将以递归地使用越来越负的数字调用自己，永远不会达到 0，并且您最终会耗尽堆栈空间。不过，如何最好地处理这个问题可能超出了您的问题范围。

递归的概念并不局限于任何特定的语言。函数调用自身背后的想法。

让我们考虑一下你的例子：阶乘函数。但现在让我们把实现放在一边，用更抽象的术语来思考它。该函数由两个元素组成：

i( 说明如何计算元素"n"。

ii( 说明如何计算初始元素

那么我们如何计算阶乘的元素n呢？我们取n并将其乘以前一个元素的阶乘： n-1 ：

n

* 阶乘(n-1(

而且只有一个初始项目：0 .也就是说，n == 0结果是1或换句话说，Factorial(0)给出了1。

您提供的算法实际上包含这两个步骤

if (x == 0) 
    return 1;                      // Do this when calculating Factorial of 0
else
    return x * Factorial (x-1);    // Do this when calculating an element n

还行。现在，当我们想要计算 4 的阶乘时会发生什么？让我们将其分解为具体步骤。

Factorial(4) -> 4 * Factorial(4-1) -> 4 * Factorial(3)

我们调用了4阶乘。所以我们用 4 乘以 4-1 的阶乘。为了得到 4-1 的阶乘，我们再次调用阶乘函数：

Factorial(3) -> 3 * Factorial(3-1) -> 3 * Factorial(2)

现在我们需要计算 2 的阶乘。

Factorial(2) -> 2 * Factorial(2-1) -> 2 * Factorial(1)

和 1

Factorial(1) -> 1 * Factorial(1-1) -> 1 * Factorial(0)

请注意，现在我们必须计算 0 的阶乘。但这里我们有一个特殊的指令：如果参数为 0，则结果必须是 1。让我们回顾一下我们的计算：

Factorial(0)为 1。替换阶乘 1 的计算中的结果。

Factorial(1) -> 1 * Factorial(1-1) -> 1 * 1也是 1

Factorial(2) -> 2 * Factorial(1) -> 2 * 1 -> 2

Factorial(3) -> 3 * Factorial(2) -> 3 * 2 -> 6

Factorial(4) -> 4 * Factorial(3) -> 4 * 3 -> 12

你提到了以下解释：

每次输入方法时，都会在堆栈上分配一个新的 int， 每次方法退出时，都会解除分配 int。

当我们进入函数内部计算前一个数字的阶乘时Factorial这些步骤是必须在堆栈上分配一个新的 int：对于 4 的阶乘，数字 4 进入堆栈，算法计算 3 的阶乘，依此类推。当我们到达 0 的阶乘的最后时，我们终于可以开始解除分配数字了。我们有 0 的阶乘，将结果乘以 1。返回 1 的阶乘，解除分配 1。同样的情况发生在 2、3 和最后的 4 上。

希望澄清整个概念。我知道解释很广泛，但另一方面，一开始就很难掌握它，所以我宁愿太彻底。

它是递归的，因为这里的语句：

return x * Factorial (x-1);

返回 x * 的结果，调用阶乘 (X-1( 的结果... 它呼唤自己得到答案。当 x==0 时，它只需返回值 1 即可脱离循环。

但有一点需要注意，x==0 将值返回给谁？ 答案很可能是累积值的循环。

方法 Factorial 再次调用自身，从 5 开始，递减参数 (x-1(，直到传递的参数 x 为 0。

因此，对阶乘的第一次调用传递 5，第二次调用 4、3、2、1、0。

计算结果是：5*4*3*2*1 = 120。

它正在做的是反复调用自己。

实际上正在发生的事情如下。

我们输入阶乘时 x 等于 5，由于我们大于 0，我们将 5 乘以再次调用我们的自我(阶乘(的结果是 5 - 1，即 4。在这个递归调用中，我们发现我们自己在用 4 - 1 做另一个递归调用，即 3。我们反复执行此操作，直到我们用 0 调用阶乘，其中它返回 1。然后 1 返回到

递归，递归将其乘以 2，递归返回递归，递归将其乘以 3，然后下一个乘以 4，然后下一个乘以 5。

最后，返回 1 * 2 * 3 * 4 * 5 的结果，即 120。

每次调用阶乘都有一个调用要返回。 这些是在 x == 0 之后展开的递归调用。

我认为如果您稍微修改代码，这可能更容易看到，即使只是暂时的：

static int Factorial (int x)
{
    if (x == 0) return 1;
    else
    {
         int y = x * Factorial (x-1);
         return y;
    }
}

感谢您对我的问题的所有出色回复。 我现在对这段代码有了更好的理解，并意识到我需要在我的 TO-DO 列表中对递归进行更深入的研究。

相关文章：