Python06-1递归

Python06-1递归 递归（recursion）：

什么是递归？
函数自身调用自身

案例：求0~100的和

def get_count(n):
	"""
		函数返回[0, n]的和
	"""
	if n <= 0:
		return 0
	return n + get_count(n-1)

⏰ 注意：递归必须要存在终止条件，否则就是一个死循环，而且递归是自身调用自身

在Java等编程语言，如果递归没有终止条件，或者递归的层数太深，则可能出现Stack Overflow错误，该错误表示栈溢出错误（栈的内容空间不够了）

但是在Python、Javascript等编程中，一般都会规定递归的层数，默认都是1000层也可以修改默认的层数

import sys
sys.getrecursionlimit()				#获取默认的递归层数
sys.setrecursionlimit(num)			#重新设置递归的最深层数

递归的实际使用

​ 斐波那契数列：从第三个数开始，每一个是前两项数之和

def get_fibonacii(n):
	if n <= 1:
		return 1
	if n == 2:
		return 2
	return get_fibonacii(n-1) + get_fibonacii(n-2)

课堂练习：

1.上楼梯问题：
有人上楼梯，每一次可以上一个台阶或两个台阶，当到达第n个台阶是，一共有多少中走法？

def get_stairs(n):
	"""
	上楼梯问题(与斐波那契数列问题类似)：
		有人上楼梯，每一次可以上一个台阶或两个台阶，
		当到达第n个台阶是，一共有多少中走法？
	"""
	if n == 2:
		return 2
	if n == 1:
		return 1
	return get_stairs(n-1) + get_stairs(n-2)

2.不死兔子：
小明高考结束，考上了清华，父母很开心，所以买了一对刚刚出生的兔子，一对刚刚出生的兔子，经过四个月的成长就可以成长成年兔子，成年兔子每个月生一对兔子，假设兔子一直不死，问，当第n月时，共有多少对兔子

def get_rabbits(n):
	"""
		小明高考结束，考上了清华，父母很开心，所以买了一对刚刚
		出生的兔子，一对刚刚出生的兔子，经过四个月的成长就可以
		成长成年兔子，成年兔子每个月生一对兔子，假设兔子一直不死，
		问，当第n月时，共有多少对兔子
		1 1 1 1 2 3 4 5 7 10 14 19
		f(n) = f(n-1) + f(n-4)
	"""
	if n <= 4:
		return 1
	return get_rabbits(n-1) + get_rabbits(n-4)