知识源于沉淀 调用通常发生在不同的函数之间。其实调用函数有一种特殊的方式，就是调用自己，这叫递归函数调用。递归也是编程中的常用技巧，甚至是一种思维方式，非常值得掌握。
本文选自《Python极简课堂笔记:数据分析与机器学习导论》一书，将和我们一起探讨函数的递归，并在文末和大家一起分析Google经典递归面试题。
01
感性知识的递归
在解释递归的抽象概念之前，我们先回顾一下过去。
小时候，我们缠着长辈讲故事的时候，他们可能会用下面的故事“忽悠”我们:
从前，有一座山，山里有一座庙。在寺庙里，有一个老和尚正在给一个小和尚讲故事！有什么故事？从前，有一座山，山里有一座庙。寺庙里，一个老和尚在给一个小和尚讲故事！有什么故事？
……
除非讲故事的人自己停止说话，否则故事可以无限地进行下去，因为故事中嵌套的故事就是故事本身，这是语言中递归的一个例子。
但由于这个故事没有终止条件，实际上陷入了死循环，所以不符合编程领域定义的“递归”。
在编程领域，递归是指函数(或方法)直接或间接调用自身的操作，如下图所示。递归调用的好处是可以大大减少代码量，把原来复杂的问题简化成一个简单的基本操作来完成。在编程过程中，“递归调用”是一项非常实用的技能。
递归示意图
从上图可以看出，一个函数无论是直接调用自己还是间接调用自己，都是一个无止境的过程。在编程中，很明显这种没有终止的调用是不可能发生的。因此，在编写递归算法时，读者要特别注意，所有的递归都必须有终止条件，也就是所谓的递归退出。如果递归函数缺少递归出口，那么在执行时就会陷入无限循环。递归退出通常可以通过if语句来设置。当满足一定条件时，不会继续，会调用一个值结束递归。
谷歌拥有世界上最聪明的程序员。他们不仅聪明，而且有自己的“冷幽默”，独树一帜。举个例子，如果你不知道什么是“递归”，不妨去谷歌搜索一下这个关键词。然后你会发现Google除了给出必要的搜索结果外，还给出“你在找:递归”的提示，如下图所示。
谷歌程序员的“冷幽默”乍一看，你可能会想，这个谷歌搜索有问题吗？我真正明确无误地询问的是“递归”。你还有什么建议？
其实这就是谷歌搜索引擎背后程序员的“冷幽默”:如果你点击了提示“递归”，搜索引擎就会再次搜索“递归”——相当于调用自己——这不就是递归的本质吗？
也许你理解了，微笑了，但你可能还是会疑惑:这不是真的。所有递归都有终止条件。如果一直点击提示“递归”，查询不是会无限进行下去吗？
别担心，你不会一直点击的。因为递归的出口恰恰是，询问者最终知道了什么是递归，停止了询问。你是唯一知道的人。
02
递归思维和递归思维
Recurse广泛应用于计算机领域。它不仅是一种计算方法，更是一种思维方式。科技作家吴军博士认为递归思维是人类和计算机思维最大的区别之一。著名计算机科学家L. Peter Deutsch甚至认为迭代是人，递归是除(迭代是人，递归是神)。
对于计算机从业者来说，要想成为顶尖人才，做计算机相关的工作必须要有递归思维。对于普通人来说，这种思维方式也很有启发。所以，无论从哪个角度看，递归思维都是值得培养和掌握的。
人们的常规思维叫做递归思维。在汉语中，“递归”与“递归”只有一字之差，但在英语世界中，两者的差别却是如此之大，可谓“微乎其微，差之千里”。
先说递归。比如我们小时候学会从1，2，3数到100，就是典型的递归。同样，我们在学习的过程中也是循序渐进，起点是积极的，由易到难，由小到大，由局部到整体。递归是人类本能的积极思维，我们很熟悉。“递归”有一些反常识。
我们以一个整数的阶乘计算为例，来说明两种思维的区别。
如果用人类常用的递归方式计算一个整数的阶乘，比如5！= 1× 2× 3× 4× 5，那么做法就是从小到大一个接一个地相乘。如果计算10的阶乘(10！)，过程也差不多，就是从1到10。
在生活中，这种做法不仅合理，而且自然。其实中学学的数学归纳法(利用n成立时的结论推导n+1)就是一种递归的方法。为了简单起见，我们还是用阶乘这个简单的例子来说明递归的原理。
计算机如何计算阶乘？它倒过来了。
比如，数到5！，电脑会把它变成5 x 4！(即5乘以4的阶乘)。当然我们可能会质疑，4！我还不知道！不过没关系，电脑会用同样的方法放4！就变成4×3了！。至于3！，它由相同的算法处理。最终实现1！当计算机知道1！= 1(这是递归的终止条件)，此后没有向下扩展。下一步是推回所有的结果。因为我知道1！顺水推舟，你就知道2！，然后知道3！、4!还有五！。
从上面描述的递归过程可以看出，递归的方法论可以总结为两步:首先是自上而下的展开，然后是自下而上的逐步回溯。
03
递归调用的函数
你可能会问，计算机为什么要这样做？这样有什么好处？
答案并不复杂，递归可以让算法的逻辑变得非常简单。因为递归过程的每一步都使用相同的算法，所以计算机只需要从上到下重复一遍。阶乘的计算无非是某个数n的阶乘，变成这个数乘以n-1的阶乘。所以递归有两个规则:一个是自顶向下(直接从目标开始)，一个是不断重复。
递归的另一个特点是只关心它下一层的细节，而不关心下一层的细节。你可以理解递归的简单性来源于它只关注“当下”，把握“小趋势”。虽然每一步都很简单，但你总能在追求中获得属于自己独特的精彩。
我们以阶乘的计算为例，分别用递归和递归来实现。大家都能理解他们之间的区别。
【范例】利用递推和递归方式分别计算n！
1#计算阶乘2 defe iterative _ fact(n):3 fact = 14 for iinrange(1，n+1): 5fact * = i6returnfact78 #计算阶乘9defrecursive _ fact (n): 10IFN
【操作结果】
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是另一种。那么这样的过程会有多少呢？
个案分析
这个问题显然不简单，很难通过正穷举法完全遍历。解决这个问题的技巧就是使用递归。我们假设有F(20)条不同的路径计数到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)。因此，仅靠积极穷尽法，基本不可能列举出所有的情况。
以上面试问题来自曾经就职于谷歌的吴军博士。吴军博士在分析这个面试问题时指出，等价原理是数学和计算机中一个非常重要的原理。很多问题的表象看似复杂，但剥开之后本质是等价的。比如一个楼梯有20级台阶，你可以一次爬一级台阶休息一下，也可以爬两级台阶休息一下。爬到20级台阶有几种休息方法？这个问题的解其实和“谁先抢到20”一样，也是一个斐波那契数列。
从某种程度上来说，递归思维是一种以结果为导向，向后寻找，直到到达原点(递归的终止条件)的思维方式。一旦解决了原点问题，后续问题也就迎刃而解了。
本文节选自新书《Python极简课堂笔记:一本书中的数据分析和机器学习导论》。
作者:张玉红
本书秉承零入门、可读性高、注重实战的理念，全面涵盖了NumPy、Pandas、Matplolib、Seaborn、sklearn等入门数据科学必备知识。
