有趣的递归函数

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) 未定义。递归形式不能化简为solvef，所以f定义不正确

有趣的递归函数

Interesting recursive function

algorithm

recursion

complexity-theory