实用贴丨正确的「递归」打开方式:让计算机像计算机一样去计算

发布于: 4 小时前
实用贴丨正确的「递归」打开方式:让计算机像计算机一样去计算

调用通常发生在彼此不同的函数之间。其实,函数还有一种特殊的调用方式,那就是自己调用自己,这种方式称为函数递归调用。递归,在程序设计中也是一个常用的技巧,甚至是一种思维方式,非常值得我们掌握。

本文选自《Python极简讲义:一本书入门数据分析与机器学习》一书,将与我们一同探讨函数的递归,并在文末与大家分析了谷歌经典递归面试题。

01

  感性认识递归  

在讲解“递归”这个抽象概念之前,让我们来重温一下昔日往事。

小时候,当我们在缠着长辈讲故事时,长辈们可能就用下面的故事来“忽悠”我们:

从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事!故事是什么呢?从前有座山,山里有座庙,庙里有个老和尚正在给小和尚讲故事!故事是什么呢?

……

除非讲故事的人自己停下来不讲了,不然这个故事可以“无限”讲下去,原因就是“故事”嵌套的“故事”就是“故事”本身,这就是语言上“递归”的例子。

但是,由于这个故事并没有一个终止的条件,因此,它实际上是陷入了一种有头无尾的死循环,因此并不符合程序设计领域中定义的“递归”。

在程序设计领域,递归是指函数(或方法)直接或间接调用自身的一种操作,如下图所示。递归调用的好处在于,它能够大大减少代码量,将原本复杂的问题简化成一个简单的基础操作来完成。在编写程序的过程中,“递归调用”是一个非常实用的技巧。

递归示意图

从上图中可以看出,函数不论是直接调用自身,还是间接调用自身,都是一种无终止的过程。在程序设计中,显然不能出现这种无终止的调用。因此,在编写递归算法时,读者要特别注意,所有递归一定要有终止条件,这又被称作递归出口。如果一个递归函数缺少递归出口,执行时就会陷入死循环。递归出口通常可用if语句来设置,在满足某种条件时不再继续,调用某个值,结束递归。

谷歌公司有世界上最聪明的程序员。他们不光聪明,还很有自己的“冷幽默”,别出心裁。比如说,假设你不懂得什么是“递归”,不妨去谷歌搜索一下这个关键词。然后你会发现,除了给出必要的搜索结果,谷歌还给出了一条提示语“您是不是要找:递归”,如下图所示。

谷歌程序员的“冷幽默”乍一看,你可能会觉得,这谷歌搜索是不是有问题啊?我的确、明明、丝毫无误地查询的就是“递归”,还提示什么啊?

其实,这正是谷歌搜索引擎背后程序员们的“冷幽默”所在:如果你点击了那个提示“递归”,搜索引擎将再次搜索“递归”——相当于自己调用自己——这不正是递归的精髓吗?

或许你懂了,会心一笑,但可能还会疑惑:这也不对啊,所有的递归都有终止条件,如果我们一直点击这个提示词“递归”,查询岂不是会无限循环下去?

放心,你一定不会一直点击下去。因为这个递归的出口正是,查询的人终于懂得什么是递归而不再查询。而你就是那个懂得的人。

02

递推思维与递归思维

 递归 (recurse)在计算机领域被广泛应用,它不仅是一种计算方法,更是一种思维方式。科技作家吴军博士认为:递归思维是人与计算机思维最大的差别之一。著名计算机科学家彼得·多伊奇(L. Peter Deutsch)甚至认为,To iterate is human, torecurse divine(迭代是人,递归是神)

对于计算机从业者来说,想成为顶级人才,在做计算机相关工作时,必须具有递归思维。对于普通人来讲,这种思维方式也很有启发。因此,不论从哪个角度,递归思维都值得我们培养和掌握。

人的常规思维被称为递推思维。在中文里,“递推”和“递归”只有一字之差,但在英文世界里,它们的差别可大了去了,可谓“差之毫厘,谬以千里”。

我们先来说说 递推 (iterate)。比如小时候我们学习数数,从1、2、3一直数到100,就是典型的递推。类似地,我们在学习过程中循序渐进,如水到而渠成,出发点都是正向的,由易到难,由小到大,由局部到整体。递推是人类本能的正向思维,于我们而言,可谓熟稔于心。而“递归”则有一定的反常识。

下面我们以计算一个整数的阶乘为例来说明两种思维的差别。

如果用人类常用递推方式计算一个整数的阶乘,比如5!=1×2×3×4×5,那么做法是从小到大一个数一个数接连相乘。如果计算10的阶乘(10!),过程也是类似的,即从1乘到10。

在生活中,这种做法不仅合情合理,而且浑然天成。事实上,在中学里学的数学归纳法(利用当n成立时的结论,推导n+1)就是递推方法。为了简单起见,我们还是用前面求阶乘的简单例子来说明递归的原理。

计算机是怎么计算阶乘的呢?它是倒着来的。

比如要算5!,计算机就把它变成5×4!(即5乘以4的阶乘)。当然,我们可能会质疑,4!还不知道呢!但没有关系,计算机会采用同样的方法,把4!变成4×3!。至于3!,则用同样的算法处理。最后做到1!时,计算机知道1!=1(这就是递归的终止条件),自此便不再往下扩展了。接下来,就是倒推回所有的结果。因为知道了1!,顺水推舟,就知道了2!,然后可知3!、4!和5!。

从上面描述的递归过程可以看出,递归的方法论可归结为两步:先从上向下层层展开,再从下到上一步步回溯。

03

递归调用的函数

你可能会问,计算机为何要这么算?这么算有何优势?

答案并不复杂,利用递归可以使算法的逻辑变得非常简单。因为递归过程的每一步用的都是同一个算法,计算机只需要自顶向下不断重复即可。具体到阶乘的计算,无非就是某个数字n的阶乘,变成这个数乘以n-1的阶乘。因此,递归的法则就两条:一是自顶而下(从目标直接出发),二是不断重复。

递归的另一个特点在于,它只关心自己下一层的细节,而并不关心更下层的细节。你可以理解为,递归的简单源自它只关注“当下”,把握“小趋势”,虽然每一步都简单,但一直追寻下去,也能获得自己独特的精彩。

下面我们就以计算阶乘为例,分别使用递推和递归方式实现,大家可体会二者的区别。

  • 【范例】利用递推和递归方式分别计算n!

1#用正向递推的方式计算阶乘 2def iterative_fact( n ):   3    fact = 1 4    for i in range(1, n + 1): 5        fact *= i 6    return fact 7 8#用逆向递归的方式计算阶乘 9def recursive_fact( n ):10    if n <= 1 :11        return n;12    return n * recursive_fact(n - 1)1314#调用递推方法计算15num = 516result = iterative_fact( num );17print("递推方法:{}!= {}".format(num, result))18#调用递归方法计算19result = recursive_fact(num)20print("递归方法:{}!= {}".format(num, result))

【运行结果】

1递推方法:5!= 1202递归方法:5!= 120

递归函数的优点在于,定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但正向递推(即循环)的逻辑不如逆向递归的逻辑清晰。

04

谷歌公司的递归面试题

有这么一个游戏:有两个人,第一个人先从1和2中挑一个数字,第二个人可以在对方的基础上选择加1或者加2,然后又轮到第一个人,他也可以选择加1或者加2,之后再把选择权交给对方,就这样双方交替地选择加1或者加2,谁先加到20,谁就赢了。对于这个游戏,你用什么策略保证一定能赢?

✔ 案例分析   

如果用正向的递推思维(比如说穷举法),并不容易想清楚,而且还容易漏掉合理的解。但如果用逆向的递归思维,问题的解就非常容易推导出来。我们先从结果出发,如果要想抢到20,就需要抢到17,因为抢到了17,无论对方是加1还是加2,你都可以加到20。而要想抢到17,就要抢到14,以此类推,就必须抢到11、8、5和2。

因此对于这道题,只要第一个人抢到了2,他就赢定了。这是因为,无论对方选择加1还是加2,他都可以让这一轮两个人加起来的数值等于5。同样的道理,在当前和为5的基础上,无论对方选择加1或加2,他都能让和向着8进发。以此类推,整个过程都被他牢牢控制,最终的数列之和,毫无悬念地被他锁定在20。

当然谷歌的面试题并非这么简单,如果你答对第一道题,那么紧接着就会有下一道题。

按照上述方法,在不考虑谁输谁赢的情况下,从开始(以1或2为起点)加到20,有多少种不同的递加过程?比如1,4,7,10,12,15,18,20算一种;2,5,8,11,14,17,20又是一种。那么一共会有多少种这样的过程呢?

✔ 案例分析  

这道题显然并不简单,通过正向的穷举法很难完备遍历。解这道题的技巧还是要使用递归。我们假定数到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)只有一个可能,就是1,F(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)),1,2,3,5,8,13,21,……这个数列几乎按照几何级数的速度增长,到了F(20),就已经是10946了。因此,仅仅靠正向的穷举法,基本上是不可能把所有情况都列举出来的。

上述面试题来自曾就职于谷歌公司的吴军博士。吴军博士在分析这道面试题时指出,在数学和计算机上,等价性原则是一个非常重要的原则。很多问题的表象看起来纷繁复杂,但抽丝剥茧之后,其本质是等价的。比如说,如果一个楼梯有20阶,你每次可以爬一阶歇一会,也可以爬两阶歇一会,爬到20阶一共有多少种歇息法?这个问题的解,其实和“谁先抢到20”是一样的,也是一个斐波那契数列。

从某种程度上来看,递归思维是一种以结果为导向,反向追寻,直到追寻到原点(递归的终止条件)的思维方式,一旦原点问题得以解决,其后的问题都会迎刃而解。

本文节选自博文视点新书《Python极简讲义:一本书入门数据分析与机器学习》。

张玉宏 著

详情:https://u.jd.com/wvJvUn

本书秉承零入门、可读性高和注重实战的理念,全面覆盖 NumPy、Pandas、Matplolib、Seaborn、sklearn 等入门数据科学的必备知识。

破“门”而入,有如神助!

发布于: 4 小时前 阅读数: 19
用户头像

还未添加个人签名 2019.10.21 加入

还未添加个人简介

评论 (2 条评论)

发布
用户头像
感谢分享,期待更多好内容。
43 分钟前
回复
用户头像
递归思维,值得掌握~
54 分钟前
回复
没有更多了
实用贴丨正确的「递归」打开方式:让计算机像计算机一样去计算