函数的递归

2020 年 5 月 25 日

函数的递归

本文节选自张玉宏著的《Python 极简讲义:一本书入门数据分析与机器学习》,由电子工业出版社授权分享。

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

感性认识递归

在讲解“递归”这个抽象概念之前,让我们来重温一下昔日往事。小时候,当我们在缠着长辈讲故事时,长辈们可能就用下面的故事来“忽悠”我们:从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事!故事是什么呢?从前有座山,山里有座庙,庙里有个老和尚正在给小和尚讲故事!故事是什么呢……

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

但是,由于这个故事并没有一个终止的条件,因此,它实际上是陷入了一种有头无尾的死循环,因此并不符合程序设计领域中定义的“递归”。在程序设计领域,递归是指函数(或方法)直接或间接调用自身的一种操作,如下图所示。递归调用的好处在于,它能够大大减少代码量,将原本复杂的问题简化成一个简单的基础操作来完成。在编写程序的过程中,“递归调用”是一个非常实用的技巧。

递归示意图

从上图中可以看出,函数不论是直接调用自身,还是间接调用自身,都是一种无终止的过程。

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

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

谷歌程序员的“冷幽默”

乍一看,你可能会觉得,这谷歌搜索是不是有问题啊?我的确、明明、丝毫无误地查询的就是“递归”,还提示什么啊?其实,这正是谷歌搜索引擎背后程序员们的“冷幽默”所在:如果你点击了那个提示“递归”,搜索引擎将再次搜索“递归”——相当于自己调用自己——这不正是递归的精髓吗?

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

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

思维与递归思维

递归(recurse)在计算机领域被广泛应用,它不仅是一种计算方法,更是一种思维方式。科技作家吴军博士认为:递归思维是人与计算机思维最大的差别之一。著名计算机科学家彼得·多伊奇(L. Peter Deutsch)甚至认为,To iterate is human, to recurse 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!。从上面描述的递归过程可以看出,递归的方法论可归结为两步:先从上向下层层展开,再从下到上一步步回溯。

递归调用的函数

你可能会问,计算机为何要这么算?这么算有何优势?答案并不复杂,利用递归可以使算法的逻辑变得非常简单。因为递归过程的每一步用的都是同一个算法,计算机只需要自顶向下不断重复即可。

具体到阶乘的计算,无非就是某个数字 n 的阶乘,变成这个数乘以 n1 的阶乘。因此,递归的法则就两条:一是自顶而下(从目标直接出发),二是不断重复。

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

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

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

复制代码
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

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

需要注意的是,虽然递归有许多的优点,但缺点也很明显。那就是,使用递归方式需要函数做大量的压栈和弹栈操作,由于压栈和弹栈涉及函数执行上下文(context)的现场保存和现场恢复,所以程序的运行速度比不用递归实现要慢。

此外,大量的堆栈操作消耗的内存资源要比非递归调用多。而且,过深的递归调用还可能会导致堆栈溢出。如果操作不慎,还容易出现死循环。因此读者编写代码时需要多加注意,一定要设置递归操作的终止条件。

谷歌公司关于递归的面试题

有这么一个游戏:有两个人,第一个人先从 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)=1F(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”是一样的,也是一个斐波那契数列。

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

图书简介

https://u.jd.com/9WncFq

2020 年 5 月 25 日 10:00 747

评论

发布
暂无评论
发现更多内容

anyRTC 4.0 以心铸造,以梦相承

anyRTC开发者

anyRTC 4.0 官网升级

不断壮大的电竞生态——英特尔大师挑战赛携手李宁中国选手等你来战!

飞天鱼2017

第四届IMC再起烽烟 极致性能助战力升级!

飞天鱼2017

Oracle常用命令

阡陌r

week10 学习总结

耕夫

即大数据后-贵阳能否成为区块链的机遇之城?

CECBC区块链专委会

区块链 大数据 贵阳

快速学习秘诀:费曼学习法

池建强

学习方法

架构师训练营第10周

大丁💸💵💴💶🚀🐟

如何通过electron构建桌面跨平台音视频应用

ZEGO即构

音视频 Electron RTC

低/零代码的认知误区有哪些?

代码制造者

编程语言 低代码 零代码 信息化 开发应用

将设计模式应用到日常的curd中-模板方法和装饰器

LSJ

Java 设计 设计模式 装饰器 模板方法

华章科技好书5折优惠,满99再减10元

华章IT

Python AI 数字化转型 Java 25 周年 计算机科学丛书

架构师训练营第十周作业

一剑

中国计算机软件开发合同纠纷分析报告(2019-2)

朱又生

项目管理 计算机软件开发合同纠纷 风险管理 司法大数据

中国计算机软件开发合同纠纷分析报告(2019-3)

朱又生

项目管理 计算机软件开发合同纠纷 风险管理 司法大数据

第十周总结

晨光

娱乐至穷

北柯

学习 互联网 娱乐 抖音

信息管理软件需求分析阶段的实践经验及论述(2010年)

朱又生

项目管理 产品经理 需求分析 用户需求调研

软件规模扩张与其组织粒度的进化

superman

中台 微服务 服务化改造

SpreadJS 纯前端表格控件应用案例:医疗行业智能报表系统

Geek_Willie

微服务

石印掌纹

SpreadJS 纯前端表格控件应用案例:生产采购管理软件

Geek_Willie

央行清算总中心与三家银行签署区块链福费廷交易平台合作协议

CECBC区块链专委会

区块链技术 人民银行

RushPlayer“一键下马”系列之-JavPlayer

flow

第十周作业

晨光

只加两行代码,为什么用了整整两天时间?

程序员生活志

编程 bug

35岁腾讯员工被裁员感叹:北京一套房,存款700多万,失业好焦虑

程序员生活志

程序员生活

Linux神器strace的使用方法及实践

华为云开发者社区

Linux 运维 工具 后端 Strace

微服务的认识

chenzt

IMC御用设备到底有多强?英特尔携手掠夺者呈现“飞”一般5GHz电竞盛宴

飞天鱼2017

中国计算机软件开发合同纠纷分析报告(2019-1)

朱又生

项目管理 计算机软件开发合同纠纷 风险管理 司法大数据

跨越计算鸿沟:如何靠软硬件协同突破算力瓶颈?

跨越计算鸿沟:如何靠软硬件协同突破算力瓶颈?

函数的递归-InfoQ