有趣的递归函数

Question

前几天我在玩一些递归函数，我做了一个像这样的简单算法：

int f(int n) {
    if (n == 0) return 1;
    return f(f(n-1)-1) * n;
}

有趣的是它适用于 f(0), f(1), f(2), f(3) & f(4) 但不管我用什么语言或编译器，似乎没有什么可以在不导致堆栈溢出的情况下完成 f(5)。

我的问题是我如何/在哪里运行它来找到 f(5) 的解决方案，以及像这样的函数的大 O 复杂性可能是什么？

前几个结果是 1,1,2,3,8...

Answer 1

这个函数的问题是它不能保证递归会停止。如果传递给递归调用的参数f小于n（并且 >= 0），那将是可以的，但是对于 n >= 4，情况不再如此。f(4) = 8，因此在计算 时f(5)，您f使用参数进行递归调用f(4)-1，即 7。因此，在n = 5 的情况下，现在使用n = 7调用它，这并没有减少问题，而是使问题变得更大。这只会进一步爆发：为了确定f(7)，你需要f(6)，为了f(6)你需要f(5)，但这就是我们正在寻找的价值，所以这就像永远绕圈子跑。

因此，f(5)是未定义的。递归形式不能简化为solve f，因此f没有正确定义。