首先要知道什么是斐波拉契數(shù)列，像1，1，2，3，5，8，13，21……這樣，第n位的數(shù)字是第(n – 1) 位上的數(shù)+ (n – 2)位上的數(shù)的和。

這個用遞歸函數(shù)實現(xiàn)很簡單只要調(diào)用下面的函數(shù)就可以了：

def fac(n):
    if n ==1:
        return 1
    else:
        return n*fac(n-1)

?但是應用卻并不簡單，首先你得確定，這個到底是不是斐波拉契數(shù)列，如下面的例子：

應用:

有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問第十個月會有多少兔子?

?很多人一看是斐波拉契數(shù)列應用就直接調(diào)用上面代碼，

代碼:

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)


print(fib(10))

運行結果:

55

但是，我們可以很清楚的知道，第三個是4只兔子，而用這個調(diào)用還是2只。解析如下：

2 2
2 2
2（可生）+2（一個月兔） 4
2（可生）+2（二個月兔，下月可生）+2（一個月兔） 6
4（可生）+2（二個月兔，下月可生）+4（一個月兔） 10
6（可生）+4（二個月兔，下月可生） + 6（一個月兔）16

上面是兔子每個月的個數(shù)，可以看出從3月開始，每個月兔子的個數(shù)是前2個月的和，可以應用，但是第一第二個月卻要返回2，正確的代碼應該如下：

def fib(n):
    if n == 1 or n == 2:
        return 2
    return fib(n - 1) + fib(n - 2)

?一個小小的不注意，數(shù)量少了一半！所以再次提醒各位審題一定要仔細

未經(jīng)允許不得轉(zhuǎn)載：445IT之家 » Python算法：用遞歸函數(shù)實現(xiàn)斐波拉契數(shù)列應用