斐波那契数列递归与非递归实现

我们知道斐波那契数列的实现方式是，下标为1或者2时，其值就是1，当下标大于3时，则f(n) = f(n-1) + f(n-2)；下面编写了递归与非递归两种实现方式（Java代码）：

public class Fibonacci {
    public static void main(String []args) {
        System.out.println(FibonacciLoop(40));
        System.out.println(FibonacciNoLoop(40));
    }

    public static long FibonacciLoop(int index) {
        if (index <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }
        if (index == 1 || index == 2) {
            return 1;
        }
        else {
            return FibonacciLoop(index - 1) + FibonacciLoop(index - 2);
        }
    }

    public static long FibonacciNoLoop(int index) {
        if (index <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }       
        if (index == 1 || index == 2) {
            return 1;
        }

        long m = 1L;
        long n = 1L;
        long result = 0;

        for (int i = 3; i <= index; i++) {
            result = m + n;
            m = n;
            n = result;
        }

        return result;
    }
}

测试当下标为40时，结果为102334155。

斐波那契数列还有很多衍生的问题，比如青蛙跳台阶问题：

 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

可以把n级台阶时的跳法看成是n的函数，记为f(n)。
当n>2时，第一次跳的时候就有两种不同的选择：
一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);
另一种选择是第一次跳2级，此时跳法数目等于后面剩下n-2级台阶的跳法数目，即为f(n-2)。
因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。
递归与非递归的Java代码。

public static long FrogJumpLoop(int n) {
        if (n <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        else {
            return FrogJumpLoop(n - 1) + FrogJumpLoop(n - 2);
        }
    }

    public static long FrogJumpNoLoop(int n) {
        if (n <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        long step1 = 1L;
        long step2 = 2L;
        long result = 0;

        for (int i = 3; i <= n; i++) {
            result = step1 + step2;
            step1 = step2;
            step2 = result;
        }

        return result;
    }

其他关于斐波那契变形的题目可以参考博客：http://blog.csdn.net/u010177286/article/details/47129019