斐波那契的表现 [英] Performance of Fibonacci

问题描述

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

该功能在Mathematica中运行缓慢，我需要提高速度.我必须使用函数式编程和递归.我不确定为什么它运行这么慢，即使有一点点想法如何改善它也会有所帮助.

This function is running slow in Mathematica and I need to increase the speed. I have to use functional programming and recursion. I'm not sure why this is running so slow, and even the slightest idea how to improve this would be helpful.

推荐答案

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

A good way to write a faster recursive function is to have it memorize previous values. This does come at the cost of memory, of course, but it can help in cases like this. In order to calculate f[x], you calculate f[x-1] and f[x-2] - and then to calculate f[x-1], you calculate f[x-2] again; you end up recalculating a lot of values a lot of times. (Forgive my imprecision!)

要随身携带东西，可以使用以下惯用法:

To store things as you go, you can use this idiom:

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

我在这台机器上没有mathematica，但我敢肯定，没有办法这会计算出错误的值.

I don't have mathematica on this machine, but I'm pretty sure there's no way this computes the wrong value.

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

f[256]

就像我在下面的评论中说的那样，如果您还有f的其他定义，则可能要先使用Clear[f]删除它们.

Like I said in a comment below, if you have other definitions of f, you might want to wipe them out first with Clear[f].

感谢rcollyer:请注意$RecursionLimit！默认值为256.(当然，这是有充分理由的.真正的深度递归通常不是一个好主意.)

Thanks to rcollyer: Be careful about $RecursionLimit! It defaults to 256. (Of course, this is with good reason. Really deep recursion is usually a bad idea.)

这篇关于斐波那契的表现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！