algorithm - 有趣的递归函数

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 未正确定义。