注册 登录
Python基础教程

第一章: 环境搭建,安装Python

第二章: 挑选一款趁手的IDE

第三章: 计算机基础知识

第四章: 命令行基础知识

第五章: 从全局把握Python

第六章: Python语言基础

第七章: Python流程控制

第八章: Python数据类型与运算

第九章: Python字符串类型

第十章: Python列表类型

第十一章: Python元祖类型

第十二章: Python字典类型

第十三章: Python集合类型

第十四章: Python函数处理

第十五章: Python文件处理

第十六章: Python面向对象

第十七章: Python异常处理

第十八章: Python模块处理

第十九章: Python项目实战

首页 > Python基础教程 > 第十四章: Python函数处理 > 14.6节:彻底掌握递归函数

14.6节:彻底掌握递归函数

薯条老师 2020-05-22 16:30:21 206521 0

编辑 收藏

广州番禺Python, Java小班周末班培训

薯条老师的线下Python,Java小班周末班已经开课了,培训的课程有Python爬虫,Python后端开发,Python办公自动化,Python大数据分析,Java后端开发。授课详情请点击:http://chipscoco.com/?cate=6

14.6.1 理解递归函数

Python也支持定义递归函数。所谓的递归函数,是指自己调用自己的函数。这里的调用不一定是直接调用,也可以是间接地调用。

image.png


现在来举个简单的例子:


# __desc__ = 定义一个简单的递归函数
def recursive_sum(numbers): 
    # 在函数内部直接调用自己
    recursive_sum(numbers)
上文代码中定义的recursive_sum,就是一个递归函数。在函数recursive_sum内部,又继续调用了recursive_sum函数。在函数中如果调用自己,那么会形成一个调用环,递归函数的这种方式非常类似于循环结构。同学们可以通过下图进行理解:

image.png



 

在上文中定义的递归函数存在一个很严重的问题,它会不断地调用自己,消耗系统资源。将上文的代码实例在命令行中执行时,程序会异常终止:
# __desc__ = 定义一个简单的递归函数,并执行
def recursive_sum(numbers): 
    # 在函数内部直接调用自己
    recursive_sum(numbers)

# 调用该递归函数
recursive_sum([1,2,3,4,5])
执行该递归函数以后,Python会抛出递归错误的异常信息:
Traceback (most recent call last):
 File "demo.py", line 5, in <module>
   recursive_sum([1,2,3,4,5])
 File "demo.py", line 3, in recursive_sum
   recursive_sum(numbers)
 File "demo.py", line 3, in recursive_sum
   recursive_sum(numbers)
 File "demo.py", line 3, in recursive_sum
   recursive_sum(numbers)
 [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

在Python解释器的错误提示中,指示该递归函数已超出了最大递归深度。对于递归深度,同学们可以将其理解为递归函数的调用次数。

14.6.2 递归函数必须能够正常终止

在设计递归函数时,必须定义一个退出边界,否则函数会不断地递归执行,一旦超出Python语言所支持的递归深度,那么就会抛出RecursionError的错误异常。我们可以在函数体中使用控制语句加一段控制逻辑,当递归函数在条件不满足时就终止递归。所谓的终止递归,即不再调用自己。现在来写个简单的函数,逆序输出10到1之间的所有整数,使用递归函数进行实现:
# __desc__ = 定义递归函数,逆序输出10到1之间的所有整数
def count_backwards(number):
    # 当参数number大于0时,就输出number的值

    if number > 0:
        print(number)
        number -= 1
        # 不断调用自己,直到number小于等于0      
        count_backwards(number)
 
# 当参数number小于等于0时,函数将不再调用自己,此时会正常退出
 
# 执行这个递归函数
count_backwards(10)
 
""" 递归函数的输出为:
10
9
8
7
6
5
4
3
2
1
"""

14.6.3 在递归函数中返回值

递归函数较非递归函数,会更难理解,在熟练掌握了递归函数的用法以后,可以写出更加简洁的代码。现在来定义一个将列表进行求和的函数,使用非递归函数进行实现:
# __desc__ = 定义一个非递归函数,将列表进行求和
 
def accumulate(numbers):
    sum_of_numbers = 0
    for _ in numbers:
        sum_of_numbers += _
    return sum_of_numbers
 
sum_of_numbers = accumulate([1,2,3,4])
# sum_of_numbers的输出为10
定义一个将列表进行求和的函数,使用递归函数进行实现:
# __desc__ = 定义一个递归函数,将列表进行求和
 
def accumulate(numbers):
    # 递归版本只需一行代码即可实现
    return 0 if not numbers else numbers[-1]+accumulate(numbers[0:len(numbers)-1])
 
 
sum_of_numbers = accumulate([1,2,3,4])
# sum_of_numbers的输出为10
在上文的两则代码实例中,递归版的列表求和,只需要一行代码就实现了求和的功能。现在对这行代码进行详细地讲解:
(1) 该行代码最外层是一个三元运算结构:
return 0 if not numbers else numbers[-1]+accumulate(numbers[0:len(numbers)-1])
return 0 if not numbers
前面的这段代码表示,如果参数numbers为空,就返回0。
(2) 调用自己
else numbers[-1]+accumulate(numbers[0:len(numbers)-1])
后面的这段代码表示,如果列表numbers非空,那么就先取出列表最后一个元素:
numbers[-1]

然后对列表进行切片,再将切片后的列表作为参数传递给accumulate函数:
accumulate(numbers[0:len(numbers)-1])
同学们注意这个切片的语法,每次切片都将尾部的元素排除。
最后将取出的尾部元素,与递归函数的返回值进行相加:
numbers[-1]+accumulate(numbers[0:len(numbers)-1])
(3) 递归执行
由于是递归执行,所以又会重复(1)与(2)的步骤,直到满足了(1)中的条件,切片后的列表为空列表,返回0,不再调用自己。与非递归函数相比,递归函数虽然更加简洁,但是更难理解。同学们在理解递归调用的时候,可以将递归函数的执行过程,一步一步地画出来。比如先定义一个调用两次就退出的递归函数,然后将其调用过程画出来,再不断增加调用次数。

14.6.4 执行递归函数的代价

我们在定义递归函数的时候必须要设计函数的边界条件,一旦超出边界,就终止递归,否则递归函数会不断地执行,不断地消耗系统资源,直至被系统kill。递归函数的执行体也不宜过长,因为递归函数在执行的过程中,会给函数体中的变量重新分配存储空间,如果递归的深度过深,可想而知,会占用大量的内存空间,严重时会造成程序崩溃。

14.6.5 知识要点

(1) 所谓的递归函数,是指直接或间接地调用自身的函数。
(2) 在定义递归函数的时候必须设计函数的边界条件,一旦超出边界,就终止递归,否则递归函数会不断地执行,不断地消耗系统资源,直至被系统kill。

14.6.6 高薪就业班

(1) Python后端工程师高薪就业班,月薪10K-15K,免费领取课程大纲
(2) Python爬虫工程师高薪就业班,年薪十五万,免费领取课程大纲
(3) Java后端开发工程师高薪就业班,月薪10K-20K, 免费领取课程大纲
(4) Python大数据工程师就业班,月薪12K-25K,免费领取课程大纲

扫码免费领取学习资料:


欢迎 发表评论:

请登录

忘记密码我要注册

注册账号

已有账号?请登录