七、递归函数
1、在函数内部,可以调用其他函数。如果一个函数在内部调用自身,这个函数就是递归函数
2、如果一个新的调用能在相同过程中较早的调用结束之前开始,那么该过程就是递归的
3、在操作系统中,查看某一目录内所有文件、修改权限等都是递归的应用
4、使用递归函数需要注意防止栈溢出
递归特性:
1. 必须有一个明确的结束条件
2. 每次进入更深一层递归时,问题规模相比上次递归都应有所减少
3. 递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出)
>>> def func(num):
... if num == 1:
... return 1
... else:
... return num * func(num - 1)
...
>>> print func(5)
120
>>> print func(10)
3628800
或者:
#!/usr/bin/env python
#coding:utf8
def func(num):
if num == 1:
return num
return num * func(num -1)
if __name__ == "__main__":
print func(5)
print func(6)
执行结果:
120
720
为了明确递归步骤,对 5!
进行过程分解:
func(5) # 第 1 次调用使用 5
5 * func(4) # 第 2 次调用使用 4
5 * (4 * func(3)) # 第 3 次调用使用 3
5 * (4 * (3 * func(2))) # 第 4 次调用使用 2
5 * (4 * (3 * (2 * func(1)))) # 第 5 次调用使用 1
5 * (4 * (3 * (2 * 1))) # 从第 5 次调用返回
5 * (4 * (3 * 2)) # 从第 4 次调用返回
5 * (4 * 6) # 从第 3次调用返回
5 * 24 # 从第 2 次调用返回
120 # 从第 1 次调用返回
当数字减少到 1 时,递归结束
递归的优缺点:
优点:
递归使代码看起来更加整洁、优雅
可以用递归将复杂任务分解成更简单的子问题
使用递归比使用一些嵌套迭代更容易
缺点:
递归的逻辑很难调试、跟进
递归调用的代价高昂(效率低),因为占用了大量的内存和时间。
利用函数编写如下数列:
斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368...
def func(arg1,arg2):
if arg1 == 0:
print arg1, arg2
arg3 = arg1 + arg2
print arg3
func(arg2, arg3)
func(0,1)
注意:在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。
由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出
5、解决递归调用栈溢出的方法是通过尾递归优化
尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况
举个例子,我们来计算阶乘 n! = 1 x 2 x 3 x ... x n ,用函数 fact(n) 表示,可以看出:fact(n) = n! = 1 x 2 x 3 x ... x (n1) x n = (n1)! x n = fact(n1) x n
所以, fact(n) 可以表示为 n x fact(n‐1) ,只有n=1时需要特殊处理
递归函数:
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
执行结果:
>>> fact(1)
1 >
>> fact(5)
120
上面的 fact(n) 函数由于 return n * fact(n ‐ 1) 引入了乘法表达式,所以就不是尾递归了。要改成尾递归方式,需要多一点代码,
主要是要把每一步的乘积传入到递归函数中
def fact(n):
return fact_iter(n, 1)
def fact_iter(num, product):
if num == 1:
return product
return fact_iter(num - 1, num * product)
可以看到, return fact_iter(num ‐ 1, num * product) 仅返回递归函数本身, num ‐ 1 和 num * product 在函数调用前就会被计算,不影响函数调用
fact(5) 对应的 fact_iter(5, 1) 的调用如下:
===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120
尾递归调用时,如果做了优化,栈不会增长,因此,无论多少次调用也不会导致栈溢出。
遗憾的是,大多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以,即使把上面的 fact(n) 函数改成尾递归方式,也会导致栈溢出。
使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。
针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的,没有循环语句的编程语言只能通过尾递归实现循环。
Python标准的解释器没有针对尾递归做优化,任何递归函数都存在栈溢出的问题。
递归的最大深度-999
递归函数如果不受到外力的阻止会一直执行下去。但是每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了1000左右
拿什么来证明这个999理论呢?这里我们可以做一个实验:
def foo(n):
print(n)
n += 1
foo(n)
foo(1)
根据在pycharm和Linux上测试都发现:超过999都会报错
当然,这是python为了我们程序的内存优化所设定的一个默认值,我们当然还可以通过一些手段去修改它:
import sys
print(sys.setrecursionlimit(100000))
我们可以通过这种方式来修改递归的最大深度,刚刚我们将python允许的递归深度设置为了10w,至于实际可以达到的深度就取决于计算机的性能了。不过我们还是不推荐修改这个默认的递归深度。
递归函数与三级菜单
#!/usr/bin/env python #coding:utf8 menu = { '北京': { '海淀': { '五道口': { 'soho': {}, '网易': {}, 'google': {} }, '中关村': { '爱奇艺': {}, '汽车之家': {}, 'youku': {}, }, '上地': { '百度': {}, }, }, '昌平': { '沙河': { '老男孩': {}, '北航': {}, }, '天通苑': {}, '回龙观': {}, }, '朝阳': {}, '东城': {}, }, '上海': { '闵行': { "人民广场": { '炸鸡店': {} } }, '闸北': { '火车战': { '携程': {} } }, '浦东': {}, }, '山东': {}, }
def threeTM(dic): while True: for k in dic: print k #输出键,即输出北京、上海、山东 key = raw_input('input >>').strip() if key == 'b' or key == 'q': return key elif key in dic.keys() and dic[key]: ret = threeTM(dic[key]) if ret == 'q': return q threeTM(menu)
执行结果:
C:Python27python2.exe G:/PycharmProject/test/test2.py 北京 上海 山东 input >>北京 东城 朝阳 海淀 昌平 input >>海淀 五道口 中关村 上地 input >>
现在咱们用递归来写一下:
#!/usr/bin/env python #coding:utf8 menu = { '北京': { '海淀': { '五道口': { 'soho': {}, '网易': {}, 'google': {} }, '中关村': { '爱奇艺': {}, '汽车之家': {}, 'youku': {}, }, '上地': { '百度': {}, }, }, '昌平': { '沙河': { '老男孩': {}, '北航': {}, }, '天通苑': {}, '回龙观': {}, }, '朝阳': {}, '东城': {}, }, '上海': { '闵行': { "人民广场": { '炸鸡店': {} } }, '闸北': { '火车战': { '携程': {} } }, '浦东': {}, }, '山东': {}, } l = [menu]
print json.dumps(menu,encoding="utf8",ensure_ascii=False)
#{"北京": {"东城": {}, "朝阳": {}, "海淀": {"五道口": {"网易": {}, "google": {}, "soho": {}}, "中关村": {"youku": {}, "爱奇艺": {}, "汽车之家": {}}, "上地": {"百度": {}}}, "昌平": {"天通苑": {}, "沙河": {"北航": {}, "老男孩": {}}, "回龙观": {}}}, "上海": {"闵行": {"人民广场": {"炸鸡店": {}}}, "闸北": {"火车战": {"携程": {}}}, "浦东": {}}, "山东": {}}
while l: for key in l[-1]: print key k = raw_input('input>>').strip() # 北京 if k in l[-1].keys() and l[-1][k]: l.append(l[-1][k]) elif k == 'b': l.pop() elif k == 'q': break
执行结果:
北京 上海 山东 input>>北京 东城 朝阳 海淀 昌平 input>>海淀 五道口 中关村 上地 input>>五道口 网易 google soho input>>