递归函数 - 阶乘

Question

我试图围绕递归函数的阶乘计算示例，在尝试跟踪递归函数本身的流时总是迷路。它是否为每次迭代返回*（a - 1）的值？为什么它不返回值1？简单的单词只有plz newb在这里:)

// factorial calculator
#include <iostream>
using namespace std;

long factorial (long a)
{
  if (a > 1)
   return (a * factorial (a-1));
  else
   return 1;
}

int main ()
{
  long number = 9;
  cout << number << "! = " << factorial (number);
  return 0;
}

Answer 1

想象一下，在重新编写代码时，您正在重写代码行。例如，假设你打电话：

factorial(3)

在阶乘函数中，变量a的值为3.因此if条件的计算结果为true。这意味着您的整个if语句可以重写为return (a * factorial (a-1))，但值3替换a。所以你有了：

(3 * factorial (3-1))

继续，3-1将被评估离开：

(3 * factorial (2))

下一步是评估对factorial(2)的调用。在此调用中，变量a的值为2，因此if条件的计算结果为true，可以重写为：

(3 * 2 * factorial(2-1))

然后对2-1进行评估，以便得到：

(3 * 2 * factorial(1))

然后评估对factorial(1)的调用。这次a的值为1，if条件为false。这意味着它可以重写为1：

(3 * 2 * 1)

然后评估3 * 2：

(6 * 1)

然后评估6 * 1：

(6)

括号在这里没关系（但你的代码中有它们）所以这实际上是：

 6

Answer 2

因为该方法正在调用自身，因此它被称为递归。递归函数必须具有在满足条件时停止执行的代码，例如在代码中，它就是

当a <= 1时，它返回1

递归函数依赖于Stack，当你调用factorial（9）时，函数实际上说“oops，我还没有答案，但我知道factorial（9）实际上是9 * factorial（9-1）。所以借口我，我现在打电话给factorial（8）并等待，如果有什么事情在未来实际工作“

然后代码最终遇到了factorial（1），然后它停止并说“factorial of 1本身就是1”，它很清楚我将其称为递归函数的停止点。

Answer 3

停止尝试通过递归调用跟踪所有内容，并将递归函数视为实际上是函数。它有时碰巧自称。当你传递一个函数参数时，你不需要知道墙后面发生了什么。函数是正在完成的工作的抽象，并根据其参数提供正确的答案。例如，当你使用exp()或log()或cos()时，你不需要知道它是如何工作的才能使用它。

这是你必须进行信仰的递归跳跃的地方 - “如果我能相信这个功能能够为一个小问题提供正确的答案，那么我可以为我当前的问题构建答案。”对于阶乘，n的正确答案为1，等于零或一，n * factorial(n - 1)为n > 1。您可以通过为小案例编写该公式来确认这一点：

4! = 4 * 3! = 4 * (3 * 2!) = 4 * (3 * (2 * 1!)) = 4 * (3 * (2 * 1))

是的，这几乎是4的算术定义！

现在看看你发布的递归实现，略微重新排序，并看到直接的对应关系：

long factorial(long a) {  // If I trust this function...
  if (a <= 1)   // when a is 0 or 1
    return 1;   // I know the answer is 1.
  else          // Otherwise, trust the answer for the smaller case of (a-1) and 
    return (a * factorial(a-1));         // multiply that answer by a to get a!.
}

如果你愿意做出信仰的递归跳跃，那么很多其他非常复杂的函数实际上都是自己写的。