Fibonacci 解题报告 – 技术圈

Fibonacci 解题报告 – 技术圈

基于尾递归在LintCode上是能通过的，在给出代码前，先介绍尾递归：
顾名思义，尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。
下面是具体实现的代码：

public int fibonacci(int n){     if (n == 1){         return 0;     }else if(n == 2)         return 1;     else         return Tail(n, 0, 1, 3); }  private int Tail(int n, int b1, int b2, int begin){     if (n == begin){         return b1 + b2;     }else{         return Tail(n, b2, b1 + b2, begin + 1);     } }

为了加深对代码的理解，我们用一个过程来模拟：

fibonacci(7) = Tail(7, 0, 1, 3)      = Tail(7, 1, 2, 4)      = Tail(7, 2, 3, 5)      = Tail(7, 3, 5, 6)      = 8

很容易看到，整个尾递归过程，只有不断往深，但却不用不必要往回（进行相加），故对于支持尾递归的语言，其编译器会进行优化。

Read full article from Fibonacci 解题报告 – 技术圈