0

有人可以向我解释一下吗？我在 C# 中编写了一个函数来计算这样一个数字的阶乘：

public int factorial(int input)
{
    if (input == 0 || input == 1)
        return 1;
else
{
    int temp = 1;
    for (int i = 1; i <= input; i++)
        temp = temp * i;
    return temp;
    }
}

但我发现了一些 C++ 代码（我真的不知道任何 C++ 顺便说一句），它使用递归循环找到阶乘：

int factorial(int number) {
 int temp;
 if(number <= 1) return 1;
 temp = number * factorial(number - 1);
 return temp;
}

有人可以向我解释它是如何工作的吗？谢谢。

4

5 回答 5

6

好吧，它factorial(n)使用n * factorial(n - 1)了n = 1.

例如：

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1

实现只是使用这个递归定义。

于 2011-04-24T13:01:16.467 回答
2

让我们逐行分析：

if(number <= 1) return 1;
temp = number * factorial(number - 1);
return temp;

第 1 行：如果数字小于或等于 0，我们返回 1。这就是说0! = 1和1! = 1

第 2 + 3 行：否则我们返回number * factorial(number - 1). 让我们看看这个5!（这里我用作简洁n!的同义词）factorial(n)

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 3 * 1 // Here we don't have to expand 1! in the same way because of the condition

所以整个事情展开了。它只是使用该属性

n! = n * (n - 1) * ... * 2 * 1 = n * (n - 1)!

警告：与迭代（或尾递归优化）版本相比，递归代码将一如既往地遭受堆栈溢出和内存使用量增加，因此使用风险自负。

于 2011-04-24T13:02:17.097 回答
2

从语法上讲，C++ 代码与用 C# 编写的相同代码相同。不要让语言差异让您措手不及！考虑到变量是在函数顶部声明的，它对我来说实际上看起来像 C；这在 C++ 或 C# 中都不是绝对必要的。我更喜欢在第一次使用变量时声明它们，将声明和初始化组合在一个语句中，但这只是一种风格偏好，不会改变代码的功能。

我将尝试通过在代码片段的每一行添加注释来解释这一点：

// Declare a function named "Factorial" that accepts a single integer parameter,
// and returns an integer value.
int Factorial(int number)
{
    // Declare a temporary variable of type integer
    int temp;

    // This is a guard clause that returns from the function immediately
    // if the value of the argument is less than or equal to 1.
    // In that case, it simply returns a value of 1.
    // (This is important to prevent the function from recursively calling itself
    // forever, producing an infinite loop!)
    if(number <= 1) return 1;

    // Set the value of the temp variable equal to the value of the argument
    // multiplied by a recursive call to the Factorial function
    temp = number * Factorial(number - 1);

    // Return the value of the temporary variable
   return temp;
}

递归调用只是意味着函数从同一个函数中调用自身。这是有效的，因为 n 的阶乘等效于以下语句：

n! = n * (n-1)!

了解代码如何工作的一种好方法是将其添加到测试项目中，然后使用调试器单步执行代码。Visual Studio 在 C# 应用程序中对此提供了非常丰富的支持。您可以观察函数如何递归调用自身，观察每一行按顺序执行，甚至可以看到变量的值随着对它们执行操作而发生变化。

于 2011-04-24T13:03:51.303 回答
1

递归函数是在其主体中调用自身的函数。对于它是有界的，并最终返回一个值，必须发生两件事：

  1. 它必须有一个基本情况，它不会再次调用自己，返回一个已知值。此基本情况停止递归。对于阶乘函数，当输入为 0 时，此值为 1。

  2. 它的递归应用程序必须收敛到基本情况。对于阶乘，递归应用程序调用输入减去 1 的函数，最终将收敛到基本情况。

查看此函数的一种更简单的方法是（仅对正输入有效）：

int factorial(int input) {
  return input == 0 ? 1 : input * factorial(input - 1);
}
于 2011-04-24T13:10:32.580 回答
1

递归函数是从同一个函数调用的函数

例如：

  Test()
    {
      i++;
      Test();
      cout<<i;
    }

查看代码它将一次又一次地调用该函数

递归问题它将无限工作，因此希望通过特定条件停止它

上面代码的一些变化现在看起来

int i=0; 
Test()
        {
         if(i==10) return;
         i++;
         Test();
         cout<<i;
        }

output 将 10 打印 10 次，这里这行将cout<<i; 在 return 后执行

于 2011-04-24T13:53:41.060 回答