一道经典的递归题目--斐波那契数列

斐波那契数列（Fibonacci sequence），斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）是如何使用递归的呢？如何求它的第n项？

它的第n项等于它的n-1项加上n-2项。

则是：

f(n) = f(n-1) + f(n-2)
           

求第n项不断的调用这个递归函数，求前两项。递归的终止条件是这时就返回此时的值：

n == 1 or n == 2 
           

那么函数应是

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

测试函数如下：

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


while True:
	n = int(input("输入求的第n项"))
    if n == 0 :
        break
    else:
        print("斐波那契数列的第n项是：",f(n))
           

递归函数是在于找规律而进行递归，如下面这道兔子繁殖问题：

有一对兔子，4个月长大，此后的每个月可以繁殖出1对兔子，问第n月有多少对兔子。

天数     兔子对数
1           1
2		    1
3 			1
4			1
5			2
6			3	
7			4	
8			5
9			7
           

观察可以得到规律,没得出规律就多写几个。

f(n) = f(n-1) + f(n-4)
           

那么就可以得到第n天有多少对兔子：

def f(n):
    if n ==1 or n == 2 or n== 3 or n ==4:
        return 1
    return f(n-1)+f(n-4)

n = int(input("请输入天数:"))
print(f(n))    
           

主要是观察规律从而得出递归的条件，和终止条件，尽量不要让递归次数过多。

分享就到这里。