递归
一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃。
递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏,下面对此方面进行更加深入的理解
递归的分类
这里根据递归调用的数量分为线性递归、二路递归与多重递归
线性递归
如果一个递归调用最多开始一个其他递归调用,我们称之为线性递归。
例如:
def binary_search(data, target, low, high): """ 二分查找,对有序列表进行查找,如果找到则返回True,否则返回False """ if low > high: return False else: mid = (low + high) // 2 if target == data[mid]: return True elif target < data[mid]: return binary_search(data, target, low, mid - 1) else: return binary_search(data, target, mid + 1, high)
虽然在代码中有两个binary_search,但他们是不同条件执行的,每次只能执行一次,所以是线性递归。
二路递归
如果一个递归调用可以开始两个其他递归调用,我们称之为二路递归
例如:
def binary_sum(S, start, stop): """ 二路递归计算一个序列的和,例如S[0:5],就像切片的范围一样 """ if start >= stop: return 0 elif start == stop - 1: return S[start] else: mid = (start + stop) // 2 return binary_sum(S, start, mid) + binary_sum(S, mid, stop)
这个递归每次执行都会调用两次该函数,所以说是二路递归,每次递归后,范围缩小一半,所以该递归的深度是1+logn
多重递归
如果一个递归调用可以开始三个或者更多其他递归调用,我们称之为多重递归
例如:
import os def disk_usage(path): """ 计算一个文件系统的磁盘使用情况, """ total = os.path.getsize(path) if os.path.isdir(path): for filename in os.listdir(path): childpath = os.path.join(path, filename) total += disk_usage(childpath) print('{0:<7}'.format(total), path) return total
os.path.getsize为获得标识的文件或者目录使用的即时磁盘空间大小。我理解的是如果该标识的是一个文件,那么就是获得该文件的大小,如果是一个文件夹的话,那就是获得该文件夹的大小,但不包括文件夹里边的内容,就像是一个盒子中放了很多物品,但这里只计算了盒子的重量,但没有计算物品的重量,也就是计算了一个空盒子。所以这个递归函数中的递归调用次数取决于这一层文件或文件夹的数量,所以是多重递归。
递归的不足
递归的不足显然就是时间与空间的消耗 ,这篇文章中使用了缓存的方法减少了斐波那契数列的计算消耗,在这里我们使用另一种方式来改善那种坏的递归:
def fibonacci(n): """ 斐波那契数列计算,返回的是一个元组 """ if n <= 1: return (n, 0) else: (a, b) = fibonacci(n - 1) return(a + b, a)
将原来的二路递归改为了线性递归,减少了重复的计算。
python的最大递归深度
每一次递归都会有资源的消耗,每一次连续的调用都会需要额外的内存,当产生无限递归时,那就意味着资源的迅速耗尽,这明显是不合理的。python为了避免这种现象,在设计时有意的限制了递归的深度,我们可以测试一下
def limitless(n): print('第' + str(n) + '次调用') n += 1 return limitless(n) limitless(1)
第988次调用
第989次调用
第990次调用
第991次调用
第992次调用
第993次调用
第994次调用
第995次调用
第996次调用
Traceback (most recent call last):
File “D:/github/Data-Structure/code/递归.py”, line 73, in
limitless(1)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
return limitless(n)
[Previous line repeated 992 more times]
File “D:/github/Data-Structure/code/递归.py”, line 68, in limitless
print(‘第' + str(n) + ‘次调用')
RecursionError: maximum recursion depth exceeded while calling a Python object
最终递归到996次停止了递归,也就是python的递归深度限制在了1000附近。
1000层的限制已经是足够的了,但是还是有可能限制到某些计算,所以python提供了一个修改限制的方
import sys def limitless(n): print('第' + str(n) + '次调用') n += 1 return limitless(n) print(sys.getrecursionlimit())#1000 sys.setrecursionlimit(2000) limitless(1)
第1994次调用 第1995次调用 第1996次调用 Traceback (most recent call last): File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless return limitless(n) File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless return limitless(n) File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless return limitless(n) [Previous line repeated 995 more times] File “D:/github/Data-Structure/code/递归.py”, line 68, in limitless print(‘第' + str(n) + ‘次调用') RecursionError: maximum recursion depth exceeded while calling a Python objec
可见把这个深度该为2000后便多了1000次调用,但这个深度显然不是设置多少就是多少,毕竟还有计算机CPU与内存的限制,比如吧深度改为10000,那么运行后
第3920次调用
第3921次调用
第3922次调用
第3923次调用
Process finished with exit code -1073741571 (0xC00000FD)
到达3923次便终止了,查询-1073741571发现是递归栈溢出的问题。
尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。
Python解释器在对于一次函数调用中,会使用一个栈帧来保存当前调用的函数的信息,如输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。因此在递归的调用中,这种未执行完的函数会一层一层的占用大量的栈帧。如果将递归的调用放到函数执行的最后一步,那么执行完这步,该次函数的栈帧就会释放,调用函数的新栈帧就会替换掉之前的栈帧,所以无论调用的深度有多少次,都只会占用一个栈帧,那也就不会发生栈溢出的问题。这就是尾递归。
所以根据需要,尾递归必须是线性递归,并且递归调用的返回值必须立即返回。
拿一个阶乘递归函数举例
def factorial(n): """ 阶乘递归函数 """ if n == 0: return 1 else: return n * factorial(n - 1)
上边这个是一个普通的递归,下面把他改成尾递归的形式
def facttail(n, res): """ 阶乘尾递归,res初始为1 """ if n < 0: return 0 elif n == 0: return 1 elif n == 1: return res else: return facttail(n - 1, n *res)
这个函数比之前那个还多了个res,第一种每次调用完要乘n,这里的res就起了相同的作用,由于尾递归每一层的栈帧要释放,所以通过res来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计,因为它的前提条件就是调用后什么也不再执行了,所以要作为传递的东西就得提前通过参数设计传递,总之要想设计一个尾递归的算法还是需要好好思考一下的。
Python,递归
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。
更新动态
- DzintraErliha-Dreamscape(2024)[24Bit-96kHz]FLAC
- 群星.1999-上华世纪国语总冠军4CD【上华】【WAV+CUE】
- 叶丽仪.1992-仙鹤神针电视剧原声音乐专辑【星传真】【WAV+CUE】
- 陈柏宇.2011-QUINQUENNIUM【SONY】【WAV+CUE】
- 《51首热门当红歌曲 十大顶级发烧女声 3CD》[WAV+CUE][1.6GB]
- 《赵传 深受摇滚迷青睐的台湾音乐人 约定》[WAV+CUE][320MB]
- 《庄心妍 实力唱将 发烧音乐精选集》[WAV+CUE][380MB]
- [音展纪念碟]2006年《TAA台湾第十六届国际HI-ENDHI-FI音响展》2cd[WAV]
- 中国音乐地图之听见西藏山歌牧歌酒歌2020[WAV分轨]
- 王宏伟2017-永远的红飘带[太平洋影音][WAV+CUE]
- 费翔.1997-NOW现在【第一中国】【WAV+CUE】
- 新格合唱团.1981-我唱你和2辑(滚石新格民歌系列)【新格】【WAV+CUE】
- 陈柏宇.2011-QUINQUENNIUM【SONY】【WAV+CUE】
- 雨果唱片-《金唛系列-蔷薇依韵琼瑶》WAV
- 陈百强《凝望(2012华纳LPCD45限量版)[DMI]》[WAV整轨]