递归优化？

Question

为什么Fibonacci递归程序工作这么久？

这是在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个斐波纳契数.)