面试中，问得比较多的几个问题之一，求斐波那契数列f(n)？

斐波那契数列是这样一个数列，它满足：

到底有几种方法，这些思路里蕴含的优化思路究竟是怎么样的，今天和大家聊一聊。

思路 ：这是一个递归的代码，非常清晰，直接把斐波那契数列的定义翻译成了代码。

可以看到，计算f(5)和f(4)中都要计算f(3)，但这 两次f(3)会重复计算 ，这就是递归的最大问题，对于同一个f(a)，不能复用。

计算一个f(n)到底需要有多少次递归调用呢？

我们可以在代码里 加一个计数 验证一下。