斐波那契的变化？

Question

我在某处偶然发现了以下方法/功能。我最初认为它是一个递归的斐波那契函数，但它不是。知道这个功能是做什么的或者它的目的是什么吗？

int recursive(int n)
{
    if (n > 1)
        return (n * recursive(n - 1)) +
               ((n - 1) * recursive(n - 2));
    else
    {
        return 1;
    }
}

更新：基于@user3386109 的评论：这是后续问题：我怀疑有人可能试图使用它而不是 n 的阶乘，这对于更大的数字来说变得非常慢。但是即使这个函数对于较大的 n 也会变慢，因为它的时间复杂度为 O(2^n)。你认为可以有另一种方法来找到接近 n 的阶乘或正好是 n 的阶乘的东西，它不会随着 n

的较大值而减慢

Answer 1

这是 OEIS 序列 A000225。

recursive(n) 计算没有子串 [k,k+1] 的 [1,...,n+1] 的排列。

如果您点击 OEIS 链接，还有各种其他公式可以得到相同的答案，以及由同一组数字描述的其他内容。

要更快地运行代码，请使用记忆（就像使用斐波那契一样），这样您就不会多次重新计算相同的值。您还可以向前迭代（即从 f(1) 和 f(2) 开始，并在计算下一个值时始终将最后一个 2 保留在内存中，直到达到目标）。

这是前向版本（Ruby；dk Python）

def f(n)
  arr = [, 1, 1]
  3.upto(n) do |i|
    # same logic: recursive[i] = (i * recursive(i - 1)) + ((i - 1) * recursive(i - 2));
    arr[i%3] = i * arr[(i-1)%3] + (i-1) *  arr[(i-2)%3]
  end
  return arr[n % 3]
end

Answer 2

如果你的目标是让函数更快，有一个简单的方法：用你一个一个构建的结果列表替换递归调用。

这是 python 示例：

def f(n):
    if n > 1:
        return n * f(n-1) + (n-1) * f(n-2)
    return 1

def fast_f(n):
    if n < 2:
        return 1
    results = [1, 1]
    for i in range(2, n+1):
        new_result = i * results[-1] + (i-1) * results[-2]
        results.append(new_result)
    return results[-1]

for i in range(0, 5):
    print('')
    print(f"f({i}) = {f(i)}")
    print(f"fast_f({i}) = {fast_f(i)}")

你得到：

fast_f 的时间复杂度为 O(N) 而不是 O(2^N)

注0：这个函数呈指数增长。您期望 N 作为输入的结果是 N 位数字（例如，如果 N 是 1000，您将得到一个由大约 1000 位数字组成的数字......）。你可能不得不使用大整数。

注 1： 如果您多次调用 f，而不是执行

res_0 = f(x0)

然后

res_1 = f(x1)

执行：

max_x = max(x0, x1)

然后构建结果列表直到 max_x 然后提取每次调用的结果：

res_0 = results[x0]; res_1 = results[x1]

。它会更快。

注 2： 可能可以用一个非递归的数学表达式来表达结果。如果你想这样做，你需要做这样的事情：数学归纳（它变成了一道数学题，可能做不出来）。但即使你成功得到类似这样的东西：

f(n) = n! + 3*n + 7

（这是一个例子），时间复杂度仍然是 O(N)，因为阶乘和指数表达式是 O(N)。