递归通常用于问题递推得解，因其 基于用户栈实现，也常用来控制执行顺序。由于虚拟地址空间的内存限制，过多的调用栈帧可能触发栈溢出/OOM，通常将递归改为迭代减小调用开销避免。本文着重解析递归调用思想、顺序控制和调用流程追踪
递归
问题的解若可表示为递推关系，形如 \scriptsize F(n) = G(F(n-1))，问题的解便可由开始状态 `$$\scriptsize F(s) = S 经由关系式递推得到
步骤与构成
1）找到问题的递推关系式 \scriptsize F(n) = G(F(n-1))
2）明确进入子问题前和完成子问题后需要完成的计算
3）明确当前问题传给子问题的参数、获得子问题的结果、回传父问题的结果
4）确定递归边界 \scriptsize F(s) = S
逻辑后置与倒序处理
递归体中，递归调用过程先于逻辑执行，从而使得开始计算本层逻辑时，后序问题均已计算完毕；一般用于 倒序处理
public Result preRecursion(Param param) { // 递归边界 bound(); // 后续问题计算先于本层执行逻辑 Result res = preRecursion(new Param()); // 每层执行逻辑时均基于后续已计算完成的结果 Result doneResult = process(res); // 返回父问题当前层处理结果 return doneResult; }
逻辑前置与正序处理
递归体中，逻辑执行先于递归调用过程，从而使得开始计算本层逻辑时，前序问题均已计算完毕；一般用于 正序处理；全局问题解决完毕时在每层问题末尾逐层向前返回同一个结果，又称为尾递归
public Result postRecursion(Param param) { // 递归边界 bound(); // 本层运算逻辑先于后续运算 process(); // 后序运算均基于已计算结果，返回时逐层向前传递问题解 return postRecursion(new Param()); }
递归一般形式
综合首递归和尾递归，递归调用前置逻辑用来 基于前序运算正序处理元素，调用后置逻辑用来 基于后序运算倒序处理元素
public Result recursion(Result lastResult) { // 递归边界 bound(); // 父问题进入子问题前，基于前序运算已完成的操作 preOperation(lastResult); // 父问题向子问题传入预定参数，子问题运算完毕后返回后序运算结果 Result subResult = recursion(new Param()); // 子问题处理完毕后回到父问题，基于后序运算计算 doneResult = postOperation(subResult); // 向父问题返回当前问题处理完毕的结果 return doneResult; }
案例详析
汉诺塔问题
- 递推关系分析：
+ 若要移动最下层的第N个元素，必须先移走上面更小的N-1个元素，问题转化为移动第N-1个元素的子问题：由于子问题元素均小于父问题元素，所以只要先解决子问题，元素在柱间的移动就不会违反大小关系
+ 若要使起始柱的最大元素置于目标柱底，目标柱必空或必已放置当前最大元素N，即限制了更小的N-1个元素必须全部位于中转柱
+ 综上父问题定义为：将N个元素经由中转柱搬至目标柱；父问题分解为：上N-1个元素从起始柱 -> 中转柱、N从起始柱 -> 目标柱、上N-1个元素从中转柱 -> 目标柱
- 明确递归边界：
+ 当前元素是顶端最小元素时（此时N=1），将其从调用时的源柱顶端移至目标柱
- 逻辑放置顺序：
+ 中转N-1元素子问题 前置于 移动本层最大元素逻辑：保证先处理更小元素，以及倒序回到本层逻辑时，N-1个元素均搬运完毕
+ 回传N-1元素子问题 后置于 移动本层最大元素逻辑：保证正序处理子问题时，目标柱当前顶层已经是当前最大元素，且在移动N-1个元素时，仍然保证先处理更小元素
\tiny
汉诺塔问题的调用次数推导如下：\\
递归调用同满二叉树的中序遍历，调用次数同其节点数量，满足递推关系\\
a_n = 2a_{n-1} + 1, a_1 = 1\\
则a_n通项可作如下推导\\
a_n = 2a_{n-1} + 1 \\
= 2(2a_{n-2} + 1) + 1\\
= 2^{n-1}a_1 + (1+2+2^2+\cdots+2^{n-2})\\
= 2^{n-1} + 2^{n-1} - 1\\
= 2^n - 1三阶汉诺塔问题的递归调用追踪如下，读者可自行画出4阶调用轨迹方便理解
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
int n = A.size();
move(n, A, B, C);
}
/**
* 把最大元素上面的n-1个元素从src经由tmp移至tar
*/
public void move(int n, List<Integer> src, List<Integer> tmp, List<Integer> tar) {
// 递归边界，将本层起始柱顶端元素移至目标柱顶端
if (n == 1) {
tar.add(src.remove(src.size() - 1));
return;
}
// 将本层最大元素上面的n-1个元素从src移到tmp
move(n - 1, src, tar, tmp);
// 将本层最大元素从src移到tar，本层最大是src[src.size() - 1]，非全局最大src[0]
tar.add(src.remove(src.size() - 1));
// 把最大元素上面的n-1个元素从tmp移到tar
move(n - 1, tmp, src, tar);
}
}两两交换链表结点
分析
> 父子问题递推
父问题 -> head -> next -> 子问题
父问题 -> next -> head -> 子问题
每一层返给父问题头结点，拿到子问题头结点
> 每层核心逻辑
交换两个结点，返回当前头结点给父问题，指向子结点返回的头结点
> 递归边界
空结点或只剩一个结点无法交换
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}数字回文序列
public void mystery(int x) {
System.out.print(x % 10);
if ((x / 10) != 0) {
mystery(x / 10);
}
System.out.print(x % 10);
}> 1234 43211234
杨辉三角
> 递推关系
if(j == 0 || j == i) father.add(1);
else father.add(sub.get(j-1) + sub.get(j));
① [改进] 从首行开始每次保存上行结果供当前行计算，避免递减递归造成的重复计算
public static List<Integer> getRow(int rowIndex) {
List<Integer> pre = new ArrayList<Integer>();
for (int i = 1; i <= rowIndex; i++) {
List<Integer> now = new ArrayList<Integer>();
for (int j = 0; j < i; j++) {
if (j == 0 || j == i - 1) now.add(1);
else now.add(pre.get(j - 1) + pre.get(j));
}
pre = now;
}
return pre;
}② [改进] 复用同一个list，减少新建list开销
public static List<Integer> getRow(int n) {
List<Integer> res = new ArrayList<>(n);
res.add(1);
int pre = res.get(0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
int tmp = res.get(j);
res.set(j, tmp + pre);
pre = tmp;
}
res.add(1);
}
return res;
}③ [改进] 倒序去除覆盖，减少中间变量开销
public static List<Integer> getRow(int n) {
List<Integer> res = new ArrayList<>(n);
res.add(1);
int pre = res.get(0);
for (int i = 1; i < n; i++) {
for (int j = i - 1; j > 0; j--) {
cur.set(j, cur.get(j - 1) + cur.get(j));
}
cur.add(1);
}
return res;
}④ [计算] 组合数公式
public List<Integer> getRow(int rowIndex) {
List<Integer> ans = new ArrayList<>();
int n = rowIndex;
for (int k = 0; k <= n; k++)
ans.add(C(n, k));
return ans;
}
private int C(int n, int k) {
long res = 1;
for (int i = 1; i <= k; i++)
res = res * (n - k + i) / i;
return (int) res;
}⑤ [计算] 组合数公式简化
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<>();
int n = rowIndex;
long pre = 1;
ans.add(1);
for (int k = 1; k <= N; k++) {
long now = pre * (n - k + 1) / k;
ans.add((int) now);
pre = now;
}
return res;
}上述若采用pre*=(n-k+1)/k，右侧结果先计算为0，导致末位为0
可利用对称性进行进一步优化
反转链表
分析
> 父子问题递推
子问题返回后一结点 -> 当前结点 -> 返回父问题头/尾结点
> 递归边界
空结点返回空或只剩一个结点返回该结点① [递归] 返回父问题头节点，每次插入需要遍历到尾节点
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode node = reverseList(head.next);
head.next = null;
ListNode temp = node;
while (temp.next != null) temp = temp.next;
temp.next = head;
return node;
}② [递归] 返回父问题尾节点，一个附加结点保存头结点，避免遍历
private static ListNode headNode = null;
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return headNode = head;
ListNode node = reverseList(head.next);
head.next = null;
node.next = head;
return head;
}③ [递归] 每一步指向之前结点，每一步都返给父问题结果的头结点
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}④ [尾递归] 返回父问题头结点，保存上一结点供指向和next指针供向后遍历
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
private static ListNode reverse(ListNode pre,ListNode cur){
if(cur == null) return pre;
ListNode next = cur.next;
cur.next = pre;
return reverse(cur,next);
}全排列问题
给定n个字符，求其字典序/升序全排列
字典序[暴力求解]
1.问题分解：
枚举当前字符 枚举下一个字符
2.问题模式：
全排列 = 当前枚举字符 + 不含当前所有字符的枚举
3.递归边界：
枚举到达给定字符集末尾
4.核心操作
按序遍历字符集，设定未出现字符为下一个字符- 代码流程
-1
-1 ×
-2 √
-1 ×
-2 ×
-3 √
-3 √
-1 ×
-2 √
-3 ×
-2
-1 √
-1 ×
-2 ×
-3 √
-2 ×
-3 √
-1 √
-2 ×
-3 ×
-3
-1 √
-1 ×
-2 √
-3 ×
-2 √
-1 √
-2 ×
-3 ×
-3 × private static char[] arr = new char[]{'c', 'b', 'a'};
public static void main(String[] args) {
char[] des = new char[arr.length];
Arrays.sort(arr);
permutation(des, 0);
}
public static void permutation(char[] des, int cur) {
if (cur == des.length) {
System.out.println(Arrays.toString(des));
}
for (char item : arr) {
int i = 0;
for (; i < cur; i++) {
if (des[i] == item) {
break;
}
}
if (i == cur) {
des[cur] = item;
permutation(des, cur + 1);
}
}
}[a, b, c]
[a, c, b]
[b, a, c]
[b, c, a]
[c, a, b]
[c, b, a]非字典序[递归交换]
分析
> 父子问题递推
父问题 = 选定某字符开头 + 子问题除该字符已排列结果 并还原选定前状态
> 每层核心逻辑
在子问题已排好基础前枚举每个字符，将当前层排列好的基础传给父问题- 代码流程
-1与1交换首位
-2与3交换首位
-2与3交换恢复原位
-1交换恢复原位
-2与1交换首位
-1与3交换首位
-1与3交换恢复原位
-2交换恢复原位
-3与1交换首位
-2与3交换首位
-2与3交换恢复原位
-3交换恢复原位 public static void main(String[] args) {
char[] arr = new char[]{'1', '2', '3', '4'};
int end = arr.length - 1;
permutation(arr, 0, end);
}
public static void permutation(char[] arr, int cur, int end) {
if (cur == end) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = cur; i <= end; i++) {
swap(arr, i, cur);
permutation(arr, cur + 1, end);
swap(arr, i, cur);
}
}
public static void swap(char[] arr, int cur, int end) {
char temp = arr[cur];
arr[cur] = arr[end];
arr[end] = temp;
}- 实际流程
-1
-2
-3
4
-4
3
-3
-2
-4
-4
-2
-4
-3
-2
-2
-3
-2
-1
-3
-4
-4
-3
-3
-1
-4
-4
-1
-4
-3
-2
-1
-3
-3
-2
-1
-4
-4
-1
-1
-2
-4
-4
-2
-4
-1
-2
-2
-1
-4
-2
-3
-1
-1
-3
-3
-2
-1
-1
-2
-1
-3
-2
-2
-3记忆化
将第一次的计算结果存储在哈希表中，通过查表法避免递归中的重复运算斐波那契数列
① 递归哈希表缓存减少计算成本
public static HashMap<Integer, Integer> cache = new HashMap<>();
public static int fib(int N) {
if (cache.containsKey(N)) return cache.get(N);
int result;
if (N < 2) result = N;
else result = fib(N - 1) + fib(N - 2);
cache.put(N, result);
return result;
}② 斐波那契数原始计算方法
public int climbStairs(int n) {
if(n < 3) return n;
int result0 = 0;
int result1 = 1;
int result = 0;
for(int i = 2; i <= n; i++){
result = result1 + result0;
result0 = result1;
result1 = result;
}
return result;
}③ 斐波那契数列计算公式
public int climbStairs(int n) {
double sqrt5 = Math.sqrt(5);
double fib = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return (int)(fib / sqrt5);
}爬楼梯
分析
当前位置种数 = 退一步数位置种数 + 退两步数位置种数
递归边界 走一步1=1，走两步2=1+1或2=2
实际数字规律为斐波那契数列，可用上例所有方法① 缓存递归
Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public int climbStairs(int n) {
if(cache.containsKey(n)) return cache.get(n);
int result;
if(n < 3) result = n;
else result = climbStairs(n - 1) + climbStairs(n - 2);
cache.put(n, result);
return result;
}② 动态规划
public static int climbStairs(int n) {
if(n < 3) return n;
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[n - 1];
}