recursion - 递归优化？

Question

为什么斐波那契递归过程可以工作这么长时间？

这是在 OCaml 中：

let rec fib n = if n<2 then n else fib (n-1) + fib (n-2);;

这是在 Mathematica 中：

Fib[n_] := If[n < 2, n, Fib[n - 1] + Fib[n - 2]]

这是在Java中：

public static BigInteger fib(long n) {
    if( n < 2 ) {
        return BigInteger.valueOf(n);
    }
    else {
        return fib(n-1).add(fib(n-2));
    }
}

因为n=100它可以工作很长时间，因为我猜它会2^100及时跟踪带有节点的树。

虽然只有 100 个数字要生成，所以它只消耗 100 个内存寄存器和 100 个计算节拍。

因此，可以优化执行。

这个任务是关于什么的，它是如何解决的？由于解决方案没有在 Mathematica 中实现，它可能不存在。关于这个问题的研究如何？

Answer 1

这是一个用来展示memoization价值的经典例子。因此，这是使其运行速度更快的一种方法。

（如果你只是想快速计算斐波那契，当然可以非常容易地重写函数以非常快速地得到答案。从 0 开始，一直到 n，每次传递前 2 个斐波那契数。）

Answer 2

我认为要走的路是记忆化，就像@JeffreyScofield 的回答一样。定义 ：

Fib2[n_] := Fib2[n] = If[n < 2, n, Fib2[n - 1] + Fib2[n - 2]]

查看 ：

Fib[30] // AbsoluteTiming
(* {9.202920, 832040} *)

Fib2[30] // AbsoluteTiming
(* {0., 832040} *)

Fib2[100] // AbsoluteTiming
(* {0.001000, 354224848179261915075} *)

Answer 3

对于递归斐波那契数列，即使 n=100 也不应该花费太多时间来操作。无论它是递归的还是迭代的，它仍然应该在 O(N) 时间内执行，因为它所做的只是总结之前在恒定时间内完成的数字。计算大约需要多长时间？