最新消息:欢迎光临 魔力 • Python!大家可以点开导航菜单中的【学习目录】,这个目录类似图书目录,更加方便学习!

Python3萌新入门笔记(21)

Python教程 小楼一夜听春语 1864浏览 0评论

这一篇教程的学习目标是了解什么是递归(Recursion)。

简单来说,递归就是函数自己调用自己。(听起来…好淫荡…)

但是,自己调用自己不会变成无限循环调用么?

例如下面这个代码:

def recursion():
    return recursion()

recursion()

代码运行后会抛出异常,RecursionError: maximum recursion depth exceeded

意思是,递归错误:超过最大递归深度

也就是说,因为函数不停的循环调用自身超过了一定次数导致的异常。

这种叫无穷递归(Infinite Recursion),一般来说并没有什么用。

我们需要有用的递归。

比较经典的应用有阶乘运算、幂运算和二分查询(看到这些词语别晕,实际上很简单)。

我们先来看阶乘运算。

阶乘:一个正整数的阶乘是所有小于及等于该数的正整数的积

举例来说,5的阶乘就是5*4*3*2*1,4的阶乘就是4*3*2*1。

其实,阶乘的运算如果不使用递归我们也可以实现。

示例代码:

def factorial(n):
    result = n 
    for i in range(1, n): 
        result *= i
    return result

print(factorial(5)) # 显示输出结果为:120

然后,我们来看使用递归方式的实现。

示例代码:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1) # 函数中调用函数自身

print(factorial(5)) # 显示输出结果为:120

递归方式实现的阶乘,好像有些不太容易理解。

我们把计算过程中,参数变量的值通过print语句显示出来看一下。

修改后的代码:

def factorial(n):
    print(n)  # 显示输出参数值
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

factorial(5)

当我们运行代码,得到如下结果:

这意味着print语句被执行了5次,同时也意味着函数被调用了5次。

先记下这个特点,我们继续通过print语句把每次通过return语句计算的结果也显示出来。

修改后代码如下:

def factorial(n):
    if n == 1:
        print('1')  # 显示输出当前的阶乘结果
        return 1
    else:
        current = n * factorial(n - 1)
        print(current)  # 显示输出当前的阶乘结果
        return current

factorial(5)

当我们运行代码,得到如下结果:

这个结果意味着,每次调用函数都会进行一次计算,并且将计算结果通过return语句返回。

但是,递归的具体执行过程仍然很模糊。

我们来看一个示意图。

上方5个色块,是代码调用了5此函数。

每次调用函数都会创建新的命名空间,大家可以理解为程序执行了5个同名的函数。

既然执行了5个函数,就有参数传入和返回结果的过程。

我们先来看调用函数时,参数传入的过程。

  • 函数首次调用时,参数n的值为5;
  • 首次调用函数的return语句中,进行了第二次调用函数,并设置参数为n-1;所以,在第二次调用的函数中,参数n的值变成了4;
  • 以此类推,直至终止调用函数自身为止。

接下来,我们再来看返回函数执行结果的过程。

  • 程序调用5次函数的同时,进行了参数的传入,第5次调用时,参数n的值是1,;此时,参数数值满足n == 1的条件,不再继续调用函数自身,通过return语句返回值,也就是1;
  • 当1这个值被返回,程序回到了倒数第2次函数调用的return语句,此时语句中对函数的最后一次调用变成了具体的值(1),和变量n相乘之后,作为返回值,再次返回给倒数第3次函数调用的return语句中;
  • 以此类推,直至返回到首次调用的函数为止。

所以,在我们刚才的运行结果截图中,我们能够到,参数的显示结果是5、4、3、2、1的顺序(依次调用函数的顺序);而返回值的显示结果是1、2、6、24、120的顺序(从最后一次调用函数向前返回计算结果的顺序)。

所以,递归可以这么理解,它就是函数循环调用函数自身;递是指在循环调用的过程中,将参数进下一次函数的调用;归是指当满足终止循环调用函数的条件时,按照和调用时相反的顺序,将函数的执行结果依次回归。

接下来,我们再来看一下幂的计算。

例如,2的4次方实际上是2*2*2*2的乘积。

示例代码:

def power(x, y):  # 定义函数计算参数x的y次方
    if y == 1:  # 满足条件时终止函数循环调用
        return x  # 参数x的1次方返回参数x
    else:
        return x * power(x, y - 1)  # 调用函数自身形成递归

print(power(2, 4))  # 显示输出结果为:16

上方代码中,当我们调用函数power时,函数开始循环调用函数自身,并且依次将参数y(3,2,1)传入每次调用的函数中,当参数y为1的时候,结束函数自身的循环调用,并且依次返回值(2,4,8,16)。

最后,我们再来看一下二分查询的案例。

例如,有一个0~100的数字列表,从中查询到一个指定的数字。

示例代码:

def search(seq, number, lower, upper):  # 定义函数,参数seq为要查询的序列,参数number为要查询的数字
    # 参数lower为查找区间的下限值,参数upper为查找区间的上限值
    if lower == upper:  # 查找区间仅剩一个数字时,即找到查询结果,停止循环调用
        assert number != seq[upper], '这里有问题!'  # 如果不相等会抛出异常AssertionError(断言错误),可以尝试把"=="改为"!="
        print(str(lower))  # 显示输出结果为:66
    else:  # 查找区间有多个数字时,继续查找
        middle = (lower + upper) // 2  # 通过整除计算,获取查找区间数字的中间值
        if number > seq[middle]:  # 判断查找的数字是否大于中间值
            return search(seq, number, middle + 1, upper)  # 如果大于中间值,中间值作为查找区间下限值,继续查找
        else:
            return search(seq, number, lower, middle)  # 如果小于中间值,中间值作为查找区间上限值,继续查找


search(range(0, 100), 66, 0, 100)  # 显示输出结果为:66

大家根据代码中的注释对递归过程进行理解,在此不再赘述。

不过在上方代码中,我添加了一个assert关键字,此关键字为断言,可以帮助我们运行程序检查语句中的错误。

使用格式为:assert 表达式, ‘自定义的异常说明字符串’

自定义的异常说明字符串可以省略,未省略时,字符串和表达式之间必须用逗号(,)分隔。

如果断言语句中的表达式出现错误,则会抛出AssertionError异常。

如果自定义了异常说明字符串,则会显示“AssertionError:自定义的异常说明字符串”。

本节知识点:

1、函数的递归;

2、断言的使用。

本节英文单词与中文释义:

1、recursion:递归

2、Infinite:无穷

3、maximum:最大值

4、depth:深度

5、exceeded:超过

6、factorial:阶乘

7、search:查询

8、power:幂

9、lower:下方

10、upper:上方

11、middle:中间

12、assert/assertion:异常

练习:根据给定的姓名,在列表中查询姓名的序号(0-68)。

lst=[‘邢佳栋’,’李学庆’,’高昊’,’潘粤明’,’戴军’,’薛之谦’,’贾宏声’,’于波’,’李连杰’,’王斑’,’蓝雨’,’刘恩佑’,’任泉’,’李光洁’,’姜文’,’黑龙’,’张殿菲’,’邓超’,’张杰’,’杨坤’,’沙溢’,’李茂’,’黄磊’,’于小伟’,’刘冠翔’,’秦俊杰’,’张琳’,’陈坤’,’黄觉’,’邵峰’,’陈旭’,’马天宇’,’杨子’,’邓安奇’,’赵鸿飞’,’马可’,’黄海波’,’黄志忠’,’李晨’,’后弦’,’王挺’,’何炅’,’朱亚文’,’胡军’,’许亚军’,’张涵予’,’贾乃亮’,’陆虎’,’印小天’,’于和伟’,’田亮’,’夏雨’,’李亚鹏’,’胡兵’,’王睿’,’保剑锋’,’于震’,’苏醒’,’胡夏’,’张丰毅’,’刘翔’,’李玉刚’,’林依轮’,’袁弘’,’朱雨辰’,’丁志诚’,’黄征’,’张子健’,’许嵩’]

答案:(见评论1楼)

转载请注明:魔力Python » Python3萌新入门笔记(21)

头像
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网站 (可选)

网友最新评论 (6)

  1. 小楼一夜听春语
    def get_index(lst, str, lower, upper):
        if lower == upper:
            return upper
        else:
            middle = (lower + upper) // 2
            if str in lst[lower:middle + 1]:  # 注意:切片操作的终止位置是截取不到的,所以要+1才能正常判断。
                return get_index(lst, str, lower, middle)
            else:
                return get_index(lst, str, middle + 1, upper)
    
    print(get_index(lst, input('请输入姓名:'), 0, len(lst)))
    
    小楼一夜听春语2年前 (2017-09-08)回复
    • 头像
      def cc(lst,name,sta=0,end=len(lst)): if sta == end: return end else: mid = (sta + end) // 2 if name in lst[sta:mid + 1]: return cc(lst,name,sta,mid) else: return cc(lst,name,mid + 1,end) 研究了半天,大致明白了+1的意思,假如列表有3个元素,切片后0:1只能取出0标,但return时会把0和1标的全部运算,若不加1调用时会出错。 同时可为起始和终止点赋值 ,起为0,终为列表长度,这样调用时就不用再输这些参数,感觉GET到了,感谢小楼超帅老师
      学习使人进步3周前 (06-25)回复
  2. 头像
    有点难消化。但写的已经很清楚了。
    走路爱走神1年前 (2018-05-25)回复
  3. 头像
    a good tutorial
    alfred31年前 (2018-06-09)回复
  4. 头像
    def 查找序列(名字): print(lst.index(名字)) 查找序列(input('请输入你的名字:')) 偏题写法 ↑,这个递归钻了好久的牛角尖才想通
    66大顺6个月前 (01-04)回复
    • 头像
      lst.index(名字)是返回出列表中已存在的名字的索引,那如果列表中不存在呢?
      Lo2周前 (06-30)回复