前言

本篇将介绍递归以及函数的内置方法。

知识回顾

递归

之前我们已经讲过，函数内部可以调用其他函数。如果一个函数在内部调用自身，这个函数就是递归函数：

def func()
	print('递归函数')
	func()

这就是一个递归函数，如果你执行这段代码的话，理想中会打印无数行 递归函数。但事实上并不会… 因为目前这个递归相当于一个死循环，一直执行下去很快会将内存撑爆，而Python为了防止这种情况发生就给递归次数做了一个限制，大概是1000次（这是默认次数，有需要你也可以自己手动修改。）
…其实到这里递归就已经讲完了- –
为了显得专业一点，高端一点，实质上限制递归次数的原因是：在计算机中，函数调用是通过‘栈’这种数据结构实现的，每调用一次函数，栈就会加一层栈帧来存储这层函数的数据；函数每return一次，栈中就减少一层。因为栈的大小是有限的，如果函数调用次数太多就会导致栈溢出。
这里我们实现一个需求，阶乘。阶乘我们都学过，数学公式是: n! = n*(n-1)*(n-2)…*3*2*1
也就是：n! = n * (n-1)!，那么用递归怎么实现呢？

def  func(n):
	#判断n是否为1，是则直接返回1
	if n == 1:
		return 1
	# n的阶乘都等于n乘以(n-1)的阶乘
	return n * func(n-1)

假设n>1,第一次调用，进入第一层，先判断n是否等于1，等于直接返回1（1的阶乘就是1），不等于返回n*f(n-1)，这时候第二次调用函数，进入第二层，先判断n-1是否等于1，是就直接返回1，此时f(n-1)=1，且第二层结束，回到第一层，计算n*f(n-1),然后第一层结束；n-1不等于1，就返回 (n-1)*f(n-2)，此时第三次调用这个函数，进入第三层，注意前面两层还没有结束，第二层在等第三层的f(n-2)，第一层在等第二层的f(n-1)…以此类推，直到最后n==1，最后一层返回1，倒数第二层返回 2*f(1)，即f(2)，倒数第三层返回3*f(2)，即f(3)，…直到最后返回f(n)。
具体以f(4)来示范：

红色箭头表示每次调用函数，绿色箭头表示当前层结束返回上一层。就好比你先往弹匣里依次塞入4颗子弹，当最后一颗塞入时，扣动扳机，最后一颗子弹被打出，然后倒数第二颗塞入的上膛。
其实这也能表现出栈的特点之一就是‘后进先出’，或者‘先进后出’，只有当这一层上面的结束了，这一层才能结束。

能够理解了，我们稍微总结一下递归的特点：

• 递归必须要有一个明确的结束条件（防止死循环，报错）
• 每执行一次递归，都应该更接近你的结束条件
• 递归效率不高，递归层次过多会导致栈溢出

我们再做一个小练习：
假设有一个从小到大排列的数字列表，里面有无数个数据，使用递归找到我想要的数字，
data=[1,3,5,9,15,26,47,58,69,89,99,246,368,9854,…]

---

这里我们要用二分查找：

def func(data,num):
    if len(data) > 1:
        mid = int(len(data)/2)
        if num > data[mid]: #  说明num在列表的右半部分
            print('%s 在列表的右半部分' % num)
            func(data[mid+1:],num)  # mid+1表示不将data[mid]算入
        elif num < data[mid]: #  说明num在列表的左半部分
            print('%s 在列表的左半部分' % num)
            func(data[:mid], num) # List顾头不顾尾
        else: #  data[mid] == num
            print('已找到%s' % num)
    else: #  list中就一个数
        if data[0] == num:
            print('已找到%s' % num)
        else:
            print('列表中没有该数据')

尾递归优化

其实Python中没有实现这个优化-。-，捎带提一下，尾递归优化是为了提高递归的效率，每一次调用递归都在return 中调用。我们知道函数中遇到return都代表函数的结束，那么在return中调用函数本身，只要最后一次调用结束，那么前面的几次也就都会结束，不会在执行其他的东西。

def func();
	return func()  # 这就是尾递归

def func2():
	return n*func2() # 这里虽然在return中调用了函数本身，但最后一层返回后，还是会继续执行完n*这个事情，并没有立即结束，所以不是尾递归

函数的内置模块

这里面有详细的介绍：
Python内置方法介绍