面试中的递归算法，先收藏没准哪天就用上了！

点击上方蓝字关注我们

下面开始今天的学习～

许多公司的面试中都会或多或少涉及到一些算法相关的概念，有的只需要吹吹牛即可，有的则会递给你一张纸让你手撕一个 xx 算法，对于相关算法有很多的分类，本文将一些面试中可能会用到的递归算法进行整理，先收藏着，说不定什么时候就用到了。

递归，在程序语言中简单的理解是：方法自己调用自己。

对于递归的程序，有两个要求：

举例，对于一个 1+2+3+...+100 的程序，如果用循环写的话，程序如下：

用递归的写法则是如下：

理解了递归的基本写法和定义之后我们来看看面试中常见的一些递归算法吧~

斐波那契数列

这个应该是非常简单的一个递归的应用了，对于许多高校中讲 C 语言的时候一般都会提及，表达式为 Z = (n-2) + (n-1)，相关的递归函数也非常好写，如下：

这个问题在多个地方出现过，一个是数学建模的课程，一个是面试题目中，描述大致如下：

楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法？

很容易想到我们可以自己定义出口（爬一阶楼梯和爬两阶楼梯的走法数量）完成一个递归的算法：

但是这样在实际计算一个非常大的数字的时候就非常慢了，因为重复计算很多，导致耗时很长，所以需要对这个程序进行优化，下面的算法保存了中间结果，如果已经计算过了，那么直接返回中间结果值，如果没有，再进行递归计算，并把结果保存起来。

这样在实际运行的时候就可以在速度上有一个非常大的提升了。

也是一个非常常见的问题，其描述如下：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

这个问题看上去非常困难，实际上理解起来非常简单，为如下三步：

1.把 n-1 号盘子移动到缓冲区

2.把1号从起点移到终点

3.把缓冲区的n-1号盘子也移到终点

所以可以比较容易的写出一个递归的程序：

这类算法有一个特点，如果你很着急想掌握它，尝试通过背板的方法解决的话，很多时候会失败，因为很容易记错（例如上面的汉诺塔问题），所以对于这类递归问题还是非常建议在第一遍理解了之后再静心自己从零开始考虑一下整个的思路过程。

递归问题中想到思路本身不非常难，真正的难点在于如何优化，但是如果没有任何相关的基础想要出一个思路的话，那还真的是有点令人神情紧张的，尤其是在面试被要求手撕算法的时候。

在力扣（LeetCode）平台上我们有专项的递归算法练习题目：递归 - 力扣 (LeetCode)，欢迎大家在理解并掌握了上述算法后来我们的平台上练习，没准哪天在需要的时候就用上了，你说是不是呢？

本文作者：Nova

编辑&版式：霍霍

文中部分图片来源于网络，为非商业用途使用，如有侵权联系删除。