Python__27--递归函数与斐波那契数列

1 递归函数

自己调用自己的函数

# 递归通式：if终止条件，else第n项的通式
def fac(n):
    if n==1:                     #终止条件
        return  1
    else:
        return n*fac(n-1)        #递归调用

2 斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。 斐波那契数列指的是这样一个数列： 0，1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711…… 它的规律是：这个数列从第 3 项开始，每一项都等于前两项之和。 在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），显然，斐波那契数列是一个线性递推数列。

#1  1  2  3  5  8
def fib(n):
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        return fib(n-1)+fib(n-2)