Question

mathematica 斐波那契数列的两种方法有什么区别？

方法一：
f[1] = 1; f[2] = 1;
f[n_] := f[n - 2] + f[n - 1]
f[25]
方法二：
f[1] = 1; f[2] = 1;
f[n_] := f[n] = f[n - 2] + f[n - 1]
求解这两种方法的区别，为什么第一种算个f[103],算了我半个小时都没算出来。
我们老师说第二种语法有问题，但是又算出来了，是我们老师错了吗?
谢谢！！

Answer 1

　　首先我可以肯定地告诉你，你们老师错了！
　　第二种方法速度更快，主要区别：
　　第一种方法在计算f[103]的时候，根据斐波那契数列的定义需要知道f[102]与f[101]，而需要知道f[102]有必须知道f[101]与f[100]，依次类推，直到f[2]与f[1]，接着计算f[101]，情况与f[102]的类似，也就是说在计算第103项的时候，f[102]计算了一次，f[101]计算了两次，f[100]计算了三次，f[99]计算了四次……f[4]计算量99次，f[3]计算了100次，然后才能得出f[103]。所以这种方法最大的缺点是在计算每一项时，都必须把前面所有的项再重新全部计算一遍，尽管这些项的数值已经知道，对于较大的数，消耗的时间比较多。
　　实际上，我们仔细想一下，便会明白，在计算f[103]的时候仅需要知道f[102]与f[101]，与前100项无关，如果我们在计算的时候把中间结果存起来，那么下次再出现f[102]或者f[101]的话，可以直接用存起来的中间结果来计算，而不是把前面的100项再重新计算一遍，第二种方法就是这样的思想，所有项仅计算一次，所以在计算较大的数时，所需时间较小，值得推荐的方法。
　　Mathematica官网上给的介绍：
http://reference.wolfram.com/mathematica/tutorial/FunctionsThatRememberValuesTheyHaveFound.html