大家好呀，我是帅蛋。
今天来讲一种很重要的算法，全称叫“递上我心爱的小乌龟”，简称“递龟(归)”。
递归是算法中的劳模，应用频率很高。
你可以把它理解成一种编程技巧，它是实现很多其它高级算法的基础，像什么二叉树的遍历，深度优先搜索啥的都有它的身影。
所以递归一定要学好、吃饱，不然后面学习其它数据结构与算法必然难上加难。
我尽量讲懂，你一定要学会。
话不多说，正式开始。
什么是递归？
老规矩，学习递归，首先要知道什么是递归。
官方说法是：直接调用自己或通过一系列调用语句间接地调用自己，叫做递归。
是不是有点懵？
怎么理解呢？举个被举烂的例子。
从前有座山，山里有座庙，庙里有个花和尚，花和尚在讲故事，讲的什么故事呢？从前有座山，山里有座庙，庙里有个花和尚，花和尚在讲故事，讲的什么故事呢？从前有座山，山里有座庙，....。
看懂了么？在故事中重复提到了同样的故事，这就是递归的核心性质。
说白了，递归就是一种循环，一种自己调用自己的循环。
如果你实在觉的想不明白，你就还把它理解成函数调用了一个与自己一模一样的其它函数。
递归的条件
来写个简单的例子：
def f(x): return x + f(x - 1)
当 x = 3 时，函数的运作是下面那样：
不知道你发现了没，这个可以一直写下去，时间有多长，它可以写多长。
这种和永动机一样能干的递归叫做死循环，在代码里肯定不能这么搞，递归递归，有递还要有归，只递不归，程序分分钟崩给你看。
所以我们要在递归里加个停止调用自己的条件，让它跳出。
def f(x): if x > 0: return x + f(x - 1) return 0
加了一个判断条件后，当 x = 3 时：f(3) = 3 + f(2) = 3 + 2 + f(1) = 3 + 2 + 1 + f(0) = 3 + 2 + 1 + 0 = 6。
看懂了上面，其实递归的条件也呼之欲出了：
- 问题可以分解为多个重复的子问题（子问题仅存在数据规模的差距，比如 f(2) 和 f(1)）。
- 存在终止条件。
如何写递归代码？
编写递归的代码，只要按照递归的条件去写就好了。
即：找出重复的子问题（递推公式） + 终止条件。
比如我们来算 n!。
我们都知道 n! = 1 * 2 * 3 * ... * n 且 0! = 1。
当 n = 3 时，3! = 3 * 2 * 1。
当 n = 4 时，4! = 4 * 3 * 2 * 1。
很容易得出的递推公式就是：
f(n) = n * f(n-1)
有了递推公式，递归代码就成功了一半，剩下就是来看一下终止条件。
自然数最小的 0! = 1，所以终止条件可以是 f(0) =1。
判断是否只需要这一个终止条件，可以用较小的数测试测试一下，比如 n = 1 或者 n = 2。
PS：“判断终止条件的个数”这一步很重要，因为有时候需要两个或者多个终止条件，比如我们很熟悉的斐波那契数列，后面实战题碰到我会再讲。
当 n = 1 时，f(1) = 1 * f(0)，当 n = 2 时，f(2) = 2 * f(1)，可以看出终止条件足够。
所以代码成了：
def f(n): if n > 0: return n * f(n-1) else: return 1
虽然这是个很简单的题，但是也告诉了我们很多：涉及到递归问题，我们不要想太多，就是找出它的递推公式和终止条件。
看起来很简单，单单是找递推公式的能力，就需要你理解它的性质，看穿它的本质，以及最勤奋的多加练习。
递归の坑
坑 1：栈溢出
我在之前的文章中讲过栈这种后进先出的线性数据结构。在计算机中，当程序运行的时候，调用函数会占用一片栈的内存空间，来保存临时变量。
当调用函数时，必然会将临时变量压入栈，等函数运行结束，这些临时变量出栈。
如果是这样的话，那你想如果递归的数据规模很大，这就会造成临时变量一直在入栈，入到一定的地步，栈都被塞满了，没地方放了，就会造成栈溢出错误。
这个时候操作系统就会果断出手，强行中断程序。
那么如何避免出现“栈溢出”这种错误呢？
可以人为设置递归调用的深度，递归超过这个深度就不再继续，尽量保证程序不会崩掉。
栈是一种后进先出（Last in First Out）的数据结构，简称 LIFO。
坑 2：重复计算
很多时候使用递归的时候会产生无谓的子操作。
比如我们都知道的斐波那契数列。
它的递推公式是 f(n) = f(n-1) + f(n-2)，我来把它简单分解一下，如下图。
上图中的 f(2) 就被重复计算了，这还只是 n = 4 的情况，当 n 更大时，出现重复的会更多。
所以很多时候，用递归解决问题并不是最佳的，特别是有许多重复子问题的时候。
出现这种情况的解决办法就是“判重 + 记录结果”，就是先保存已经求解过的 f 值，然后每次新求一个 f 值的时候看下之前是否已经求解过该值，这样就可以避免重复计算。
到这的话，递归就全部讲完了。
还是那句话，学习递归最重要的是学习它的算法思想，这就需要理解它的性质，看穿它的本质，同时勤奋的多加练习。
相信臭宝们一定可以玩弄递归于股掌之中，学会了记得回来点赞在看留言么么哒～
我是帅蛋，我们下次见。
