A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

[学习交流] 【上海校区】递归

© 不二晨 金牌黑马   /  2019-3-15 16:31  /  742 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

一、什么是递归

通过一个函数,在执行过程中一次或多次调用其本身

二、递归的调用机制

1、创建活动记录

在Python中,每当一个函数被调用时,都会创建一个活动记录(或称框架)的结构来存储一些关于函数调用的过程的信息。
活动记录中包括:

命名空间:储存函数调用的参数、局部变量
函数体中当前正在执行的命令的相关信息
2、嵌套调用

当函数的执行导致嵌套函数的调用(递归调用或调用其他函数)时,前者调用的执行被挂起,其活动记录将存储源代码中的位置,这个位置是被调用函数返回后将继续执行的控制流。

三、递归的类型

1、线性递归、二路递归、多重递归

根据递归追踪的结构(不是运行时间的渐近分析),将递归定义为以下几种:

一个递归调用最多开始一个其他递归调用,称为线性递归
一个递归调用可以开始两个其他递归调用,称为二路递归
一个递归调用可以开始三个或更多其他递归调用,称为多重递归
2、尾递归

执行的任何递归调用是在这种情况下的最后操作,而且通过封闭递归(??),递归调用的返回值(如果有的话)立即返回,那么这个递归是一个尾递归

四、设计递归算法

一般来说,使用递归的算法通常具有以下形式:

对于基本情况的测试
首先测试至少一组的基本情况(至少包含一个基本情况),这些基本情况不可以使用递归而是直接被定义,以便每个可能的递归调用链最终会达到一种基本情况。
递归
若不是一种基本情况,则执行一个或多个递归调用。应该定义每个可能的递归调用,以便使调用向一种基本情况靠近。
五、递归的误用

1、糟糕的递归实现导致严重的效率底下

如,求第n个斐波那契数列
方案一

def bad_fibonacci(n):
        if n <= 1:
                return n
        else:
                return bad_fibonacci(n-2) + bad_fibonacci(n-1)
1
2
3
4
5
此递归实现导致同一个函数重复调用多次(c5调用1次c4,2次c3,3次c2,4次c1,2次c0)

通过重新定义函数的期望值,可以避免这种情况
方案二

def good_fibonacci(n):
        if n<= 1:
                return n
        else:
                (a,b) = good_fibonacci(n-1)
                return (a+b,a)
1
2
3
4
5
6
2、最大递归深度

无限递归
如果每个递归调用都执行另一个递归调用,而最终没有达到一个基本情况,我们就有一个无穷级数的此类调用。
无限递归会迅速耗尽计算资源,这不仅是因为CPU的快速使用,而且是由于每个连续调用会创建需要额外内存的活动记录。
最大递归深度
为避免无限递归,Python设计者设置了一个限制可以同时有效激活的函数的总数,一般默认设置是1000。
---------------------
【转载,仅作分享,侵删】
作者:琪仔要转行回coder
来源:CSDN
原文:https://blog.csdn.net/lllllaaa77/article/details/88078883
版权声明:本文为博主原创文章,转载请附上博文链接!

1 个回复

倒序浏览
奈斯,感谢分享
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马