Python算法：用递归函数实现斐波拉契数列应用-445IT之家

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

这个用递归函数实现很简单只要调用下面的函数就可以了：

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

但是应用却并不简单，首先你得确定，这个到底是不是斐波拉契数列，如下面的例子：

应用:

有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第十个月会有多少兔子?

很多人一看是斐波拉契数列应用就直接调用上面代码，

代码:

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


print(fib(10))

运行结果:

但是，我们可以很清楚的知道，第三个是4只兔子，而用这个调用还是2只。解析如下：

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

上面是兔子每个月的个数，可以看出从3月开始，每个月兔子的个数是前2个月的和，可以应用，但是第一第二个月却要返回2，正确的代码应该如下：

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

一个小小的不注意，数量少了一半！所以再次提醒各位审题一定要仔细

Python算法：用递归函数实现斐波拉契数列应用