有趣递归函数

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(4)-1递归调用f，它是7。所以，在n= 5的地方，现在用n= 7调用它，这不是减少问题，而是使问题更大。这只是进一步的爆炸:为了确定f(7)，您需要f(6)，对于f(6)，您需要f(5)，但这就是我们要寻找的值，所以这就像永远在循环中运行一样。

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