递归，作为算法面试中的经典考点，一直是许多初学者的难点。然而，一旦掌握了递归的核心思想和应用技巧，你会发现它不仅高效，还能极大简化复杂问题的解决过程。在各大厂的算法面试中，递归是超高频考点，也是从算法初级迈向进阶必须要跨越的一座大山。本文会详细给大家讲解递归的概念、解递归题应该掌握的基本规律、图解递归的详细过程、经典题的归纳总结以及最后如何学好递归。
什么是递归？
简单来说，递归是一种函数调用自身的编程技巧。通过将问题分解为更小的子问题，再通过递归调用不断解决这些子问题，最终达到解决整体问题的目的。递归函数通常包括三个部分：
基准（Base Case）：这是递归停止的条件。当问题已经被简化到不可再分、可以直接求解时，直接返回结果。基准确保递归不会无限进行，是问题分解的终点。
递归分解子问题（Recursive Break-down）：这是递归的核心。在这一部分，问题被分解为更小的子问题，每个子问题的结构与原问题相同，然后递归调用自身来处理这些子问题。
递归解决子问题（Recurisively Solving）：这是递归解决问题的部分。子问题的解返回给当前层，当前层做点什么，进行处理，再返回给上一层，最终得到整个问题的完整解。
读懂生活，学好递归
递归的思想是一层一层，层层递进，等级分明，递归的思想没有跨层交流来传递信息，这也是递归最大的优势。无跨层，意味着每一层都要系统化，原则化，每一层都以“同样的动作”去完成同样结构的任务。接下来我们来看一个生活中涉及到递归思想的场景，面试中涉及到递归的每一道题都有这道题的影子。
某品牌鞋的区域销售体系包含多个层级代理，分别为一级代理、二级代理、三级代理，依此类推。每一级代理既可以直接销售鞋，也可以委托下一级代理代为销售。每个代理仅向其上一级代理汇报销售数据（一级代理向总部汇报）。
总部现要求一级代理汇总其辖区内的总销售额。请问如何统计？
为了简化问题分析，现规定每级代理下面至多有两个代理(如果有多个，方法类似)。
问题分析：一级代理要统计整个区域的总销售额，只需掌握以下信息：
1.自身直接销售额。
2.两个下级代理及其所有下级的总销售额。
因此，总销售额可以表示为： 总销售额 = 自身直接销售额 + 左代理的总销售额 + 右代理的总销售额
问题分解：
自身直接销售额很容易获得。因此，一级代理可以将问题分解为两个子问题：分别计算左代理和右代理的总销售额。
同理，当二级代理接到统计任务时，他们也将总销售额表示为： 总销售额 = 自身直接销售额 + 左代理的总销售额 + 右代理的总销售额
如此，问题一级一级向下传递，直到传递到没有下级的代理为止。然后，各级代理将数据逐级返回。
经过以上的分析我们得出此题递归的核心三要素为：
基准（Base Case）：没有下级的代理（直接返回自身直接销售额）
递归分解子问题（Recursive Break-down）：每一级的总销售额 = 自身直接销售额 + 左代理的总销售额 + 右代理的总销售额。自身直接销售额容易得到，所以整个问题可以分解成两个更小的子问题：1. 左代理的总销售额是多少？2. 右代理的总销售额是多少？
递归解决子问题（Recurisively Solving）：拿到左右两个代理的总销售额，再加上自身直接销售额，得出总销售额，并将其返回给上一层级。
代码
Java 代码：
public class SalesDemo {
/*
一级代理：A
二级代理：B，C
三级代理：D，E，F，G
其中，B, C向A汇报；D, E向B汇报；F, G向C汇报；
各代理的直接销售额为(单位：万)：
A = 15, B = 6, C = 4, D = 8, E = 2, F = 1, G = 9
*/
class SalesAgent {
String name;
int directSales;
// 为了简化分析，规定最多有两个下级代理
SalesAgent left;
SalesAgent right;
SalesAgent(String name, int directSales) {
this.name = name;
this.directSales = directSales;
}
}
// 递归算法在这里运用
public int allSales(SalesAgent agent) {
// 如果代理没有下一级的代理，直接返回自身的直接销售额
if (agent.left == null && agent.right == null) {
return agent.directSales;
}
int leftSales = 0;
if (agent.left != null) {
// 如果有左代理，拿到左代理的销售总额
leftSales = allSales(agent.left);
}
int rightSales = 0;
if (agent.right != null) {
// 如果有右代理，拿到右代理的销售总额
rightSales = allSales(agent.right);
}
return agent.directSales + leftSales + rightSales;
}
// 对代理进行创建以及初始化
public SalesAgent createSalesAgents() {
SalesAgent A = new SalesAgent("A", 15);
SalesAgent B = new SalesAgent("B", 6);
SalesAgent C = new SalesAgent("C", 4);
A.left = B;
A.right = C;
SalesAgent D = new SalesAgent("D", 8);
SalesAgent E = new SalesAgent("E", 2);
B.left = D;
B.right = E;
SalesAgent F = new SalesAgent("F", 1);
SalesAgent G = new SalesAgent("G", 9);
C.left = F;
C.right = G;
return A;
}
// 测试
public static void main(String[] args) {
SalesDemo demo = new SalesDemo();
SalesAgent A = demo.createSalesAgents();
int allSales = demo.allSales(A);
System.out.println("总的销售额为：" + allSales); // 已验证，打印出45
}
}
如果递归基准选为 agent == null, 递归深度再进一层，递归代码可以更精简：
// 递归算法在这里运用
public int allSales(SalesAgent agent) {
if (agent == null) {
return 0;
}
int leftSales = allSales(agent.left);
int rightSales = allSales(agent.right);
return agent.directSales + leftSales + rightSales;
}经典案例 - n的阶乘
问题描述：用递归的方法求n的阶乘
思路分析：如何将问题 f(n) = n!分解为结构相同的更小子问题？不难想到，f(n) = f(n−1) * n。这里，f(n) 与 f(n−1) 的结构完全相同，只是输入不同。同理，f(n−1) = f(n−2) * (n−1)。通过这种分解的方式，我们已经解决了递归的分解和子问题求解两部分。
接下来要解决的是基准问题。确定基准的关键是要明确：子问题继续分解到什么程度时不需要分解，可以直接返回答案。在本题中，我们可以选择 n=1 作为基准，因为1!=1，此时无需进一步分解，直接返回结果即可。
代码:
public int factorial(int n) {
// 基准 - 在哪里停下来
if (n == 1) {
return 1;
}
// 将n的阶乘分解成子问题 n - 1 的阶乘 - 从下一层子问题得到什么
int temp = factorial(n - 1);
// 解决子问题：给上一层返回子问题的答案 - 当前层做点什么，返回什么给上一层
return n * temp;
}
public int factorial(int n) {
if (n == 1) {
return 1;
}
int temp = factorial(n - 1);
return n * temp;
}图解
经典案例 - 归并排序
归并排序（英语：Merge Sort）采用分治（Divide and Conquer）策略。首先将待排序的数组不断地分成两半，直到每个子数组只包含一个元素或者为空。这个过程被称为 “分”。然后，将两个已排序的子数组合并成一个更大的有序数组。这个过程被称为 “治” 或 “归并”。
通过以上的分析过程，我们不难得出递归的三大要素：基准，分解，求解
基准：当子数组的长度为1时，此时子数组已然有序，不可再分。
分解：将当前的子数组一分为二，让左右分别先有序。
求解：合并左右有序的数组让当前的整个数组有序
代码
public int[] mergeSort(int[] array) {
if (array == null || array.length == 0) {
return array;
}
int[] helper = new int[array.length];
mergeSort(array, helper, 0, array.length - 1);
return array;
}
private void mergeSort(int[] array, int[] helper, int left, int right) {
// 基准: 子数组的长度为1，数组有序，直接返回
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
// 将排序整个数组（子数组）分解为：先排序好左半部分，再排序好右半部分
mergeSort(array, helper, left, mid);
mergeSort(array, helper, mid + 1, right);
// 将排序好的左半部分和右半部分进行合并，这样整个数组（子数组）都已有序
merge(array, helper, left, mid, right);
}
private void merge(int[] array, int[] helper, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
helper[i] = array[i];
}
int i = left;
int j = mid + 1;
int index = left;
while (i <= mid && j <= right) {
if (helper[i] <= helper[j]) {
array[index] = helper[i];
i++;
} else {
array[index] = helper[j];
j++;
}
index++;
}
while (i <= mid) {
array[index] = helper[i];
i++;
index++;
}
while (j <= right) {
array[index] = helper[j];
j++;
index++;
}
}性能分析
一、时间复杂度
- 归并排序的时间复杂度始终为O(nlogn) ，其中 n 是待排序数组的长度。
- 归并排序的主要思想是分治，将数组不断地分成两半，直到每个子数组只有一个元素，然后再将子数组合并起来。
- 分治的过程可以用一个递归树来表示，树的高度为logn（以 2 为底），因为每次都将问题规模减半。
- 而每次合并两个子数组的时间复杂度为O(n)，因为需要遍历两个子数组的所有元素。
- 所以总的时间复杂度为O(nlogn)。
二、空间复杂度
- 归并排序的空间复杂度为O(n)。
- 在归并过程中，需要额外的空间来存储临时数组，临时数组的大小与原数组的大小相同，所以空间复杂度为O(n)。
经典案例 - 树的路径
问题描述：给定一个二叉树，返回从一个叶子节点到另一个叶子节点最大路径的和。
问题分析：
解决树的路径问题需要考虑三个核心问题：
- 你需要左右子树给你什么信息
- 当前节点拿到左右子树的信息，如何处理，返回有用的信息给上一层
- 重复1, 2, 何时停止
以上的三个问题对应递归三要素的基准、分解以及求解。那我们分别来回答以上的核心问题
- 你需要左右子树给你什么信息
需要从左子树拿到最大的单边路径，同理，需要从右子树拿到最大的单边路径。
备注：何为单边路径，从叶子节点到另一个叶子节点组成的路径会汇聚一个节点。例如路径：1 - 1 - 2 - 3 - 5。其中1 - 1 和 5 - 3都为单边路径，他们汇聚于节点2 - 当前节点拿到左右子树的信息，如何处理，返回有用的信息给上一层
a. 如果左右子树都存在单边路径，再加上当前的节点，那就组合成了一个从叶节点到另一个叶节点的路径，更新结果
b. 然后再将当前的节点拼接到左右路径较大的单边路径组合成一个新的单边路径，返回给上一层。（告诉父节点：这是到我这为止的最大单边路径，需要的话可以拿去用） - 何时停止
当节点为空的时候，返回0；0的值也不会影响如果有负数的结果，因为在上一层可以判断左右子树是否为空，从而判断是否返回了单边路径。
代码
public int maximumLeavesPath(TreeNode root) {
int[] res = {Integer.MIN_VALUE};
findLargestPath(root, res);
return res[0];
}
private int findLargestPath(TreeNode root, int[] res) {
if (root == null) {
return 0;
}
int leftLargestPath = findLargestPath(root.left, res);
int rightLargestPath = findLargestPath(root.right, res);
if (root.left != null && root.right != null) {
// 如果左右子树都不为空，说明找到一条从叶子节点到另一个叶子节点的路径，更新结果
res[0] = Math.max(res[0], leftLargestPath + rightLargestPath + root.value);
// 从左右子树中挑一个更大的路径，加上当前节点的值，返回给上一层 （告诉父节点：这是到我这为止的最大单边路径）
return root.value + Math.max(leftLargestPath, rightLargestPath);
}
// 如果左边为空，选右边的(如果右边也为空，rightLargestPath 也为0，不影响结果)；如果右边为空，选左边的；
// 再加上自己，组成一条新的单边路径，返回给上一层 （告诉父节点：这是到我这为止的最大单边路径）
return root.left == null ? rightLargestPath + root.value : leftLargestPath + root.value;
}图解
性能分析
假设这个二叉树有 n 个节点
时间复杂度为O(n), 因为每个节点都访问了一次，每次访问都是常数级操作。
空间复杂度主要来自递归栈的调用，而递归的深度取决于树的高度，n个节点的树，最差情况的高度为n, 树的每一层只有一个节点，看似一条直线，此时来自栈的空间复杂度为O(n)。如果是完全二叉树高度约为O(logn), 来自栈调用的空间复杂度为O(logn)。综上，最差情况的栈空间复杂度为O(n)。
如何学好递归
对于初学者和基础不扎实的同学学习递归常犯的错误
- 遇难而退：递归这个概念对于初学者而言不容易理解，很多同学会找一些自己学不会的理由就顺势放弃了。做任何事情贵在坚持，学递归也一样。
- 看得教程种类越多，越容易学会：这也是一种错误的观念。你缺的不是教程，而是理解，分析，训练。
掌握递归不仅需要理解其基础概念，还需要专注于几道有代表性的题目，反复推敲、研究，并通过大量练习来熟练运用递归解决算法问题。
