大家好呀，我是帅蛋。

今天来讲一种很重要的算法，全称叫“递上我心爱的小乌龟”，简称“递龟(归)”。

递归是算法中的劳模，应用频率很高。

你可以把它理解成一种编程技巧，它是实现很多其它高级算法的基础，像什么二叉树的遍历，深度优先搜索啥的都有它的身影。

所以递归一定要学好、吃饱，不然后面学习其它数据结构与算法必然难上加难。

我尽量讲懂，你一定要学会。

话不多说，正式开始。

这篇是我在牛客网连载系列 #帅蛋的数据结构与算法空间#的第 8 篇文章，欢迎大家关注。

也希望大家能够喜欢上帅蛋，多多点赞收藏，记得关注我呀！

什么是递归？

老规矩，学习递归，首先要知道什么是递归。

官方说法是：直接调用自己或通过一系列调用语句间接地调用自己，叫做递归。

是不是有点懵？

怎么理解呢？举个被举烂的例子。

从前有座山，山里有座庙，庙里有个花和尚，花和尚在讲故事，讲的什么故事呢？从前有座山，山里有座庙，庙里有个花和尚，花和尚在讲故事，讲的什么故事呢？从前有座山，山里有座庙，....。

看懂了么？在故事中重复提到了同样的故事，这就是递归的核心性质。

说白了，递归就是一种循环，一种自己调用自己的循环。

如果你实在觉的想不明白，你就还把它理解成函数调用了一个与自己一模一样的其它函数。

递归的条件

来写个简单的例子：

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 值的时候看下之前是否已经求解过该值，这样就可以避免重复计算。

到这的话，递归就全部讲完了。

还是那句话，学习递归最重要的是学习它的算法思想，这就需要理解它的性质，看穿它的本质，同时勤奋的多加练习。

相信大家一定可以玩弄递归于股掌之中。
如果你觉得我写的对你一点点儿的帮助，记得也要动动小手帮我点个赞呀！

今天的内容就这些，我们下次见啦！

❤️ 欢迎关注我，有问题，找帅蛋，我最看不得别人迷茫！

❤️ 如果你觉得有帮助,希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~

还有小小公众号 【编程文青李狗蛋】，聊聊迷茫吹吹牛皮~