斐波那契的表现

f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]

此函数在 Mathematica 中运行缓慢，我需要提高速度。我必须使用函数式编程和递归。我不确定为什么运行如此缓慢，即使有丝毫想法也可以有所帮助。

最佳答案

编写更快的递归函数的一个好方法是让它记住以前的值。当然，这确实以内存为代价，但在这种情况下它可以提供帮助。为了计算f[x]，先计算f[x-1]和f[x-2]-然后再计算f[x-1]，再计算f[x-2]；你最终会多次重新计算很多值。 (原谅我的不严谨!)

要随时存储东西，您可以使用以下习语:

f[x_] := ( f[x] = (* calculation of f[x] goes here *)  )

编辑:我在这台机器上没有 mathematica，但我很确定这不会计算出错误的值。

f[0] = 0;
f[1] = 1;
f[x_] := ( f[x] = f[x-1] + f[x-2] );

f[256]

就像我在下面的评论中所说的那样，如果您对 f 有其他定义，您可能想先用 Clear[f] 将它们清除。

感谢 rcollyer:小心 $RecursionLimit !它默认为 256。(当然，这是有充分理由的。真正的深度递归通常是一个坏主意。)

关于斐波那契的表现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4130161/