人海茫茫
相识真好

决战Python之巅(十一)

前言

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

知识回顾

递归

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

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)来示范:
决战Python之巅(十一)
红色箭头表示每次调用函数,绿色箭头表示当前层结束返回上一层。就好比你先往弹匣里依次塞入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之巅(十一)

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

赞(0) 打赏
未经允许不得转载:老康的学习空间 » 决战Python之巅(十一)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏