凡科网站建设是免费的吗,百度指数怎么看排名,图片制作pdf文件,网站自动推广软件在前面的讲解中#xff0c;函数的调用通常发生在彼此不同的函数之间。其实#xff0c;函数还有一种特殊的调用方式#xff0c;那就是自己调用自己#xff0c;这种方式称为函数递归调用。
递归#xff0c;在程序设计中也是一个常用的技巧#xff0c;甚至是一种思维方式函数的调用通常发生在彼此不同的函数之间。其实函数还有一种特殊的调用方式那就是自己调用自己这种方式称为函数递归调用。
递归在程序设计中也是一个常用的技巧甚至是一种思维方式非常值得我们掌握。
4.3.1 感性认识递推
在讲解“递归”这个抽象概念之前让我们来重温一下昔日往事。小时候当我们在缠着长辈讲故事时长辈们可能就用下面的故事来“忽悠”我们从前有座山山里有座庙庙里有个老和尚正在给小和尚讲故事故事是什么呢从前有座山山里有座庙庙里有个老和尚正在给小和尚讲故事故事是什么呢……
除非讲故事的人自己停下来不讲了不然这个故事可以“无限”讲下去原因就是“故事”嵌套的“故事”就是“故事”本身这就是语言上“递归”的例子。
但是由于这个故事并没有一个终止的条件因此它实际上是陷入了一种有头无尾的死循环因此并不符合程序设计领域中定义的“递归”。在程序设计领域递归是指函数或方法直接或间接调用自身的一种操作如图4-4所示。递归调用的好处在于它能够大大减少代码量将原本复杂的问题简化成一个简单的基础操作来完成。在编写程序的过程中“递归调用”是一个非常实用的技巧。
图4-4 递归示意图
从图4-4中可以看出函数不论是直接调用自身还是间接调用自身都是一种无终止的过程。
在程序设计中显然不能出现这种无终止的调用。因此在编写递归算法时读者要特别注意所有递归一定要有终止条件这又被称作递归出口。
如果一个递归函数缺少递归出口执行时就会陷入死循环。递归出口通常可用if语句来设置在满足某种条件时不再继续调用某个值结束递归。
谷歌公司有世界上最聪明的程序员。他们不光聪明还很有自己的“冷幽默”别出心裁。比如说假设你不懂得什么是“递归”不妨去谷歌搜索一下这个关键词。
然后你会发现除了给出必要的搜索结果谷歌还给出了一个提示语“您是不是要找递归”如图4-5所示。
图4-5 谷歌程序员的“冷幽默”
咋一看你可能会觉得这谷歌搜索是不是有问题啊我的确、明明、丝毫无误地查询的就是“递归”还提示什么啊其实这正是谷歌搜索引擎背后程序员们的“冷幽默”所在如果你点击了那个提示“递归”搜索引擎将再次搜索“递归”——相当于自己调用自己——这不正是递归的精髓吗
或许你懂了会心一笑但可能还会疑惑这也不对啊所有的递归都有终止条件如果我们一直点击这个提示词“递归”查询岂不是会无限循环下去
放心你一定不会一直点击下去。因为这个递归的出口正是查的人终于懂得什么是递归而不再查询。而你就是那个懂得的人。
4.3.2 思维与递归思维
递归recurse在计算机领域被广泛应用它不仅是一种计算方法更是一种思维方式。科技作家吴军博士认为递归思维是人与计算机思维最大的差别之一。著名计算机科学家彼得·多伊奇L. Peter Deutsch甚至认为To iterate is human, to recurse divine迭代是人递归是神。
对于计算机从业者来说想成为顶级人才在做计算机相关工作时必须具有递归思维。对于普通人来讲这种思维方式也很有启发。因此不论从哪个角度递归思维都值得我们培养和掌握。
人的常规思维被称为递推iterate思维。在中文里“递推”和“递归”只有一字之差但在英文世界里它们的差别可大了去了可谓“差之毫厘谬以千里”。
我们先来说说递推。比如小时候我们学习数数从1、2、3一直数到100就是典型的递推。类似地我们在学习过程中循序渐进如水到而渠成出发点都是正向的由易到难由小到大由局部到整体。
递推是人类本能的正向思维于我们而言可谓熟稔于心。而“递归”则有一定的反常识。
下面我们以计算一个整数的阶乘为例来说明两种思维的差别。如果用人类常用递推方式计算一个整数的阶乘比如51×2×3×4×5那么做法是从小到大一个数一个数接连相乘。如果计算10的阶乘10过程也是类似的即从1乘到10。
在生活中这种做法不仅合情合理而且浑然天成。事实上在中学里学的数学归纳法利用当n成立时的结论推导n1的方法论就是递推。
为了简单起见我们还是用前面求阶乘的简单例子来说明递归的原理。计算机是怎么计算阶乘的呢它是倒着来的。比如要算5计算机就把它变成5x4即5乘以4的阶乘。当然我们可能会质疑4还不知道呢
但没有关系计算机会采用同样的方法把4变成4x3。至于3则用同样的算法处理。最后做到1时计算机知道11这就是递归的终止条件自此便不再往下扩展了。
接下来就是倒推回所有的结果。因为由于知道了1顺水推舟就知道了2然后可知3、4和5从上面描述的递归过程可以看出递归的方法论可归结为两步先从上向下层层展开再从下到上一步步回溯。
4.3.3 递归调用的函数
你可能会问计算机为何要这么算这么算有何优势答案并不复杂因为利用递归可以使算法的逻辑变得非常简单。因为递归过程的每一步用的都是同一个算法计算机只需要自顶向下不断重复即可。
具体到阶乘的计算无非就是某个数字n的阶乘变成这个数乘以n-1的阶乘。因此递归的法则就两条一是自顶而下从目标直接出发二是不断重复。
递归的另一个特点在于它只关心自己的下一层的细节而并不关心更下层的细节。你可以理解递归的简单源自它只关注“当下”把握“小趋势”虽然每一步都简单但一直追寻下去也能获得自己独特的精彩。
下面我们就以计算阶乘为例分别使用递推和递归方式实现见【范例4-7】读者可体会二者的区别。
【范例4-7】利用递推和递归方式分别计算niterative-recursive.py。01 #用正向递推的方式计算阶乘
02 def iterative_fact( n ):
03 fact 1
04 for i in range(1, n 1):
05 fact * i
06 return fact
07
08 # 用逆向递归的方式计算阶乘
09 def recursive_fact( n ):
10 if n 1 :
11 return n;
12 return n * recursive_fact(n - 1)
13
14 #调用非递归方法计算
15 num 5
16 result iterative_fact( num );
17 print(递推方法{}! {}.format(num, result))
18 #调用递归方法计算
19 result recursive_fact(num)
20 print(递归方法{}! {}.format(num, result))
【运行结果】递推方法5! 120
递归方法5! 120
【代码分析】
第02~06行定义了一个递推计算阶乘的函数iterative_fact()函数内部采用for循环的方式来计算结果。在for循环控制过程中使用了range()函数由于range的取值区间是左闭右开的最后一个值取不到所以在第04行执行了n1操作。
第09~12行定义一个递归函数recursive_fact采用递归的方式计算结果。
第17行和第20行用到了Python的格式化输出。在Python中一切皆对象。用双引号引起来的字符串“递归方法{}! {}”实际上是一个str对象。既然是对象它就会有相应的方法成员format()就是用于格式化输出的方法因此可以通过“对象.方法名”的格式来调用合适的方法。字符串中的花括号{}表示输出占位符第1个占位符{}用于输出format()函数中第1个变量第2个占位符{}用于输出format()函数中第2个变量以此类推。
递归函数的优点在于定义简单逻辑清晰。理论上所有的递归函数都可以写成循环的方式但正向递推即循环的逻辑不如逆向递归的逻辑清晰。
对于递推的实现这里用到了前面章节中讲到的for循环语句以1为基数不断循环相乘最终得出阶乘的结果。而在递归实现的操作中这里通过对方法本身的压栈和弹栈的方式将每一层的结果逐级返回通过逐步累加求得结果。
recursive_fact(5)的计算过程如下。 recursive_fact (5)5 * recursive_fact (4)5 * (4 * recursive_fact (3))5 * (4 * (3 * recursive_fact (2)))5 * (4 * (3 * (2 * recursive_fact (1))))5 * (4 * (3 * (2 * 1)))5 * (4 * (3 * 2))5 * (4 * 6)5 * 24120
需要注意的是虽然递归有许多的优点但缺点也很明显。那就是使用递归方式需要函数做大量的压栈和弹栈操作由于压栈和弹栈涉及函数执行上下文context的现场保存和现场恢复所以程序的运行速度比不用递归实现要慢。
此外大量的堆栈操作消耗的内存资源要比非递归调用多。而且过深的递归调用还可能会导致堆栈溢出。如果操作不慎还容易出现死循环。因此读者编写代码过程中需要多加注意一定要设置递归操作的终止条件。
思考与练习一道关于递归的面试题谷歌公司
1有这么一个游戏有两个人第一个人先从1和2中挑一个数字第二个人可以在对方的基础上选择加1或者加2然后又轮到第一个人他也可以选择加1或者加2之后再把选择权交给对方就这样双方交替地选择加1或者加2谁先加到20谁就赢了。对于这个游戏你用什么策略保证一定能赢
【案例分析】
如果用正向的递推思维比如说穷举法并不容易想清楚而且还容易漏掉合理的解。但如果用逆向的递归思维问题的解就非常容易推导出来。我们先从结果出发如果要想抢到20就需要抢到17因为抢到了17无论对方是加1还是加2你都可以加到20。而要想抢到17就要抢到14以此类推就必须抢到11、8、5和2。
图4-6 计算一下共有多少种上楼梯的方法
因此对于这道题只要第一个人抢到了2他就赢定了。这是因为无论对方选择加1还是加2他都可以让这一轮两个人加起来的数值等于5。同样的道理在当前和为5的基础上无论对方选择加1或加2他都能让和向着8进发。以此类推整个过程都被他牢牢控制最终的数列之和毫无悬念地被他锁定在20。
当然谷歌的面试题并非这么简单如果你答对第一道题那么紧接着就会有下一道题。
2按照上述方法在不考虑谁输谁赢的情况下从一开始以1或2为起点加到20有多少种不同的递加过程比如1471012151820算一种25811141720又是一种。那么一共会有多少种这样的过程呢
【案例分析】
这道题显然并不简单通过正向的穷举法很难完备遍历。解这道题的技巧还是要使用递归。我们假定数到20有F(20)种不同的路径那么到达20这个数字前一步只有两个可能的情况即从18直接跳到20或者从19数到20。
由于从18跳到20和从19到20是不同的因此达到20的路径数量其实就是达到18的路径数量加上达到19的路径数量也就是说F(20)F(18)F(19)。类似地F(19)F(18)F(17)。这就是递推公式。
最后F(1)只有一个可能就是1F(2)有两个可能要么直接跳到2要么从1达到2。知道了F(1)1和F(2)2就可以知道F(3)。知道F(3)就可以知道F(4)因为F(4) F(3) F(2)以此类推一直到F(20)即可。
聪慧如你你一定看出来了这就是著名的斐波那契数列如果我们认为F(0)也等于1那么这个数列就长成这样1(F(0))123581321……这个数列几乎按照几何级数的速度增长到了F(20)就已经是10946了可利用前面的【范例3-13】来测试。因此仅仅靠正向的穷举法基本上是不可能把所有情况都列举出来的。
上述面试题来自于曾在就职于谷歌公司的吴军博士。吴军博士在分析这道面试题时指出在数学和计算机上等价性原则是一个非常重要的原则。很多问题的表象看起来纷繁复杂但抽丝剥茧之后其本质是等价的。
比如说如果一个楼梯有20阶你每次可以爬一阶歇一会也可以两阶歇一会爬到20阶一共有多少种歇息法这个问题的解其实和“谁先抢到20”是一样的也是一个斐波那契数列。
除了前面讲解的技巧本章涉及的一些思维方式也值得读者注意。从某种程度上来看递归思维是一种以结果为导向反向追寻直到追寻到原点递归的终止条件的思维方式一旦原点问题得以解决其后的问题都会迎刃而解。
你看看这是不是和埃隆·马斯克Elon Musk等人常说的“第一性原理”思想有着类似之处呢
本文部分节选自《Python极简讲义一本书入门数据分析与机器学习》(张玉宏)【摘要 书评 试读】- 京东图书item.jd.com
张玉宏著电子工业出版社2020年5月出版。更多理论推导及实战环节请参阅该书。
