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

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

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

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

應(yīng)用:

有一對(duì)兔子，從出生后第3個(gè)月起每個(gè)月都生一對(duì)兔子，小兔子長(zhǎng)到第三個(gè)月后每個(gè)月又生一對(duì)兔子，假如兔子都不死，問(wèn)第十個(gè)月會(huì)有多少兔子?

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

代碼:

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


print(fib(10))

運(yùn)行結(jié)果:

55

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

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

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

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

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

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