理解Java中递归阶乘的行为

Question

我创建了两个递归方法来计算阶乘，如下所示:

private int fact1(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * fact1(--n);

}

private int fact2(int n) {
    if (n == 0 || n == 1)
        return 1;
    return fact2(--n) * n;
}

当我调用fact1(4)时，它返回24。当我调用fact2(4)时，它返回6（编辑：不是返回18而是返回6）。我知道第二种方法是计算3 * 2 * 1，但我不明白为什么不是4 * 3 * 2 * 1。

如果我将返回值更改为...

//fact3(4) returns 60.
return (n + 1) * fact3(--n); // wrong
//fact4(4) returns 24
return fact4(--n) * (n + 1); // works

为什么这个方法会表现出这种行为？

问题是关于不同的行为。我知道n * fact(n-1)是更好的解决方式。

有人能帮我理解这个表达式的求值吗？谢谢！

- El Mestre

---

很奇怪，还没有人指出 fact2(4) 实际上是 6。 - Tamas Hegedus

Answer 1

这归结于以下表达式之间的差异：

return n * f(--n);

return f(--n) * n;

当 n = 4 时，这些表达式的计算结果如下：

return 4 * f(3);

return f(3) * 3;

因为一旦评估 --n，n 的值会减少 1。这就是前缀 -- 运算符的工作原理。

手动递归评估整个表达式可能有所帮助。首先是：

// first
return 4 * f(3);
return 4 * 3 * f(2);
return 4 * 3 * 2 * f(1);
return 4 * 3 * 2 * 1;

// second
return f(3) * 3;
return f(2) * 2 * 3;
return f(1) * 1 * 2 * 3;
return 1 * 1 * 2 * 3;

关于相关事项，猜猜这将如何被评估：

return f(n--) * n;

这将是：

return f(4) * 3;

因为这里使用了后缀--操作符：在f(...)中n求值之后将应用-1的递减。

- janos

---

在你的第二行中，当 f(3) 被计算时会发生什么行为？为什么第二次调用返回 f(2) * 3？ - El Mestre

如果你指的是 fact2(3)，那么和我第二行的逻辑相同，只不过将 n = 3，所以变成了 f(2) * 2。 - janos

你是说表达式是 (f(2) * 2) * 3 吗？它应该返回6。但在这里运行代码却返回18。 - El Mestre

实际上，是的，你一定在运行其他东西才能得到18，因为你发帖的方法分别返回24和6。 - janos

好的，我会检查。谢谢你的回答。 - El Mestre