我們知道斐波那契數(shù)列的實現(xiàn)方式是，下標(biāo)為1或者2時，其值就是1，當(dāng)下標(biāo)大于3時，則f(n) = f(n-1) + f(n-2)；下面編寫了遞歸與非遞歸兩種實現(xiàn)方式（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;
    }
}

測試當(dāng)下標(biāo)為40時，結(jié)果為102334155。

斐波那契數(shù)列還有很多衍生的問題，比如青蛙跳臺階問題：

 一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

可以把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。
當(dāng)n>2時，第一次跳的時候就有兩種不同的選擇：
一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1);
另一種選擇是第一次跳2級，此時跳法數(shù)目等于后面剩下n-2級臺階的跳法數(shù)目，即為f(n-2)。
因此，n級臺階的不同跳法的總數(shù)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;
    }

其他關(guān)于斐波那契變形的題目可以參考博客：http://blog.csdn.net/u010177286/article/details/47129019