从零开始的Linux运维屌丝之路,资源免费分享平台   运维人员首选:简单、易用、高效、安全、稳定、社区活跃的开源软件

26、Python、递归介绍

发布:蔺要红05-05分类: Python


递归:在函数的执行过程中调用自己

# -*- coding:utf-8 -*-
#递归:在函数的执行过程中调用自己
import sys
print(sys.getrecursionlimit()) #打印出递归的深度
sys.setrecursionlimit(1500) #设置递归深度
def func(n):
    print(n)
    func(n+1)
func(1)

执行结果
 
D:\python\python.exe F:/运维笔记/python/函数/递归.py
1000  #为递归深度
1
2
3
...
...
1493
1494
1495
1496
Traceback (most recent call last):
  File "F:/运维笔记/python/函数/递归.py", line 8, in func
    func(n+1)
  File "F:/运维笔记/python/函数/递归.py", line 8, in func
    func(n+1)
  File "F:/运维笔记/python/函数/递归.py", line 8, in func
    func(n+1)
  [Previous line repeated 995 more times]
  File "F:/运维笔记/python/函数/递归.py", line 7, in func
    print(n)

RecursionError: maximum recursion depth exceeded while calling a Python object #递归错误:调用Python对象时超过最大递归深度

#1-996函数执行过程中,函数还在内存里,直到结束以后,内存才会被释放
#通俗的来讲,应为每个函数在调用自己的时候,还没有退出,占内存,多了会导致内存崩溃
#本质上讲:在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧,由于栈的大小不是无限的,所以递归调用的次数过多,会导致栈溢出

递归与栈的关系

初识递归

 
# -*- coding:utf-8 -*-
def  cal(n):
    v = int(n/2)
    print(v)
    if v == 0:
        return 'Done'
    cal(v)
cal(10)

D:\python\python.exe F:/运维笔记/python/函数/递归.py
5
2
1
0
 
# -*- coding:utf-8 -*-
def  cal(n):
    v = int(n/2)
    print(v)
    if v == 0:
        return 'Done'
    cal(v)
    print(v)
cal(10)


D:\python\python.exe F:/运维笔记/python/函数/递归.py
5
2
1
0
1        #这里为何正序了
2
5



 

通过上面的例子,可以总结递归几个特点:
 

  1. 必须有一个明确的结束条件,要不就会变成死循环了,最终撑爆系统
  2. 每次进入更深一层递归时,问题规模相比上次递归都应有所减少
  3. 递归执行效率不高,递归层次过多会导致栈溢出


递归什么用

 

可以用于解决很多算法问题,把复杂的问题分成一个个小问题,一一解决。
比如求斐波那契数列、汉诺塔、多级评论树、二分查找、求阶乘等。用递归求斐波那契数列、汉诺塔 对初学者来讲可能理解起来不太容易,所以我们用阶乘和二分查找来给大家演示一下。


求阶乘
 

任何大于1的自然数n阶乘表示方法: 

n!=1×2×3×……×n 

或 

n!=n×(n-1)!

即举例:4! = 4x3x2x1 = 24 

 

# -*- coding:utf-8 -*-
def factorial(n):
    if n == 1:  # 是0的时候,就运算完了
        return 1
    return n * factorial(n - 1)  # 每次递归相乘,n值都较之前小1
d = factorial(4)
print(d)
D:\python\python.exe F:/运维笔记/python/函数/阶乘.py
24

尾递归优化
 

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。

 
# -*- coding:utf-8 -*-
def cal(n):
    print(n)
    return cal(n+1)
cal(1)

但是前面的求阶乘例子不是尾递归、因为:return n * factorial(n - 1) 还需要等待后面 factorial(n - 1) 的结果、
上面的这种递归计算最终的return操作是乘法操作。所以不是尾递归。因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值,因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定



了解尾递归的概念、但是在python解释器中并没有优化、
温馨提示如有转载或引用以上内容之必要,敬请将本文链接作为出处标注,如有侵权我会在24小时之内删除!

欢迎使用手机扫描访问本站