这种递归形式的定义容易诱导人们使用递归形式来解决问题。这里有一个陷牌：它使用递归步骤计算Fibonacci(n-1)和Fibonacci(n-2)。但是，在计算Fibonacci(n-1)时也将计算Fibonacci(n-2)。这个额外的计算代价有多大呢？

它的代价远远不止一个冗余计算：每个递归调用都触发另外两个递归调用，而这两个调用的任何一个还将触发两个递归调用，再接下去的调用也是如此。这样，冗余计算的数量增长得非常快。例如，在递归计算Fibonacci(10)时，Fibonacci(3)的值被计算了21次。但是，在递归计算 Fibonacci(30)时，Fibonacci(3)的值被计算了317811次。当然，这317811次计算所产生的结果是完全一样的，除了其中之一外，其余的纯属浪费。这个额外的开销真是相当恐怖！



如果使用一个简单循环来代替递归，这个循环的形式肯定不如递归形式符合前面菲波那契数的抽象定义，但它的效率提高了几十万倍！



当你使用递归方式实现一个函数之前，先问问你自己使用递归带来的好处是否抵得上它的代价。 而且你必须小心：这个代价可能比初看上去要大得多。-Using a recursive Fibonacci number