如何递归计算阶乘的阶乘？

Question

我遇到了以下问题： N 是非零正整数，我必须计算以下的乘积：N*(N-1)^2*(N-2)^3*..*1^N.

目前我的解决方案如下： N*myFact(N-1)*fact(N-1)

问题是我不允许使用任何帮助功能，例如 'fact()'。

编辑：在数学上它可以表示如下：N!*(N-1)! (N-2)!..*1!

Answer 1

尝试：

int myFact(int n) {
  return n == 1 ? 1 : myFact(n-1)*n;
}

Answer 2

我认为这需要通过 1 个函数来完成，即您不能自己创建 fact 辅助函数。

你可以利用 myFact(n-1) / myFact(n-2) == (n-1)!

int myFact(int n)
{
    if (n == 0 || n == 1) {
        return 1
    } else {
        // (n - 1)!
        int previousFact = myFact(n - 1) / myFact(n - 2);
        return myFact(n - 1) * previousFact * n;
    }
}

Answer 3

这个函数叫做superfactorial。递归实现是

long superFact(n) {
  if (n < 2) return 1;
  long last = superFact(n-1);
  long prev = superFact(n-2);
  return last * last / prev * n;
}

但这非常低效——需要大约 3*F(n) 次递归调用才能找到 superFact(n)，其中 F(n) 是第 n 个斐波那契数。（工作呈指数级增长。）

如何递归计算阶乘的阶乘？

How to calculate factorial of a factorial recursively?

recursion

data-structures

computer-science