Blog of AgioPan
0%

数据结构与算法自学笔记（15）- 常见经典递归过程解析

Posted on Edited on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是 038【必备】常见经典递归过程解析 的内容，总结了7道经典递归题目，涵盖了递归的核心思想和技巧，包括带路径的递归、不带路径的递归、回溯算法等重要概念。

前置知识

在学习本节内容之前，建议先熟悉以下章节：

  • 讲解017、020、021、023、036、037（这些章节都分析过递归）

重要概念

递归与回溯的关系

  • 任何递归都是DFS且非常灵活
  • 回溯这个术语并不重要，它只是递归过程中的恢复现场操作
  • 带路径的递归 vs 不带路径的递归：大部分DP和状态压缩DP可以认为是路径简化了结构

038【必备】常见经典递归过程解析

题目一：返回字符串全部子序列（去重）

问题描述

返回字符串全部子序列，子序列要求去重。

测试链接：https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a

核心思想

使用递归的方式，对于字符串中的每一个字符，我们都有两种选择：

  1. 将该字符包含在当前子序列中
  2. 不将该字符包含在当前子序列中

通过递归遍历所有这些选择，就能得到所有可能的子序列。

子序列去重

算法实现

方法一：使用列表作为路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def generatePermutation1(self, s: str) -> List[str]:
        """
        主函数，初始化并调用递归函数 f1
        """
        # 使用集合 set 来自动处理重复的子序列
        result_set = set()
        # path 使用列表来模拟 Java 的 StringBuilder，方便添加和删除字符
        path = []
        self._f1(s, 0, path, result_set)
        return sorted(list(result_set))

    def _f1(self, s: str, i: int, path: List[str], result_set: Set[str]):
        """
        递归函数，用于生成所有子序列
        s[i...]，之前决定的路径path，set收集结果时去重
        """
        # base case: 当索引 i 到达字符串末尾时，所有字符都已考虑完毕
        if i == len(s):
            result_set.add("".join(path))
        else:
            # 决策1: 选择当前字符 s[i]
            path.append(s[i])  # 加到路径中去
            self._f1(s, i + 1, path, result_set)
            
            # 回溯：撤销选择，为下一种决策做准备
            path.pop()  # 从路径中移除，删掉最后一个字符
            
            # 决策2: 不选择当前字符 s[i]
            self._f1(s, i + 1, path, result_set)

方法二：使用固定长度列表和size指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def generatePermutation2(self, s: str) -> List[str]:
        """
        主函数，初始化并调用递归函数 f2
        """
        result_set = set()
        # 预先分配一个与原字符串等长的列表作为路径容器
        path = [''] * len(s)
        self._f2(s, 0, path, 0, result_set)
        return sorted(list(result_set))

    def _f2(self, s: str, i: int, path: List[str], size: int, result_set: Set[str]):
        """
        与f1思想相同，但使用不同的方式来维护路径
        这方法不用回溯，因为path是固定长度的列表，size指针来表示有效字符长度
        """
        if i == len(s):
            # path[:size] 表示路径中的有效部分
            result_set.add("".join(path[:size]))
            # path[:size]: 取列表/序列 path 的前 size 个元素（左闭右开，不会越界，超过长度就取到末尾）
            # "".join(...): 用空字符串作为分隔符，把可迭代对象里的“字符串元素”拼接成一个整体字符串
            # result_set.add(...): 将结果添加到集合中，自动去重
        else:
            # 决策1: 选择当前字符 s[i]，将其放入 path 的 size 位置
            path[size] = s[i]
            self._f2(s, i + 1, path, size + 1, result_set) #size+1表明有效字符长度+1，指针后移
            
            # 决策2: 不选择当前字符 s[i]，直接进入下一层递归
            self._f2(s, i + 1, path, size, result_set)

算法分析

  • 时间复杂度：O(2^n × n)，子序列个数2^n，平均长度O(n)级别
  • 空间复杂度：O(2^n × n)
  • 核心技巧：递归选择 + set去重

题目二：返回数组的所有组合（去重）

问题描述

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的组合。答案不能包含重复的组合。

测试链接：https://leetcode.cn/problems/subsets-ii/

核心思想

与生成子序列（排列）不同，这里通过一次性决策一组相同数字的方式来避免重复。

  1. 先对数组排序。
  2. 在递归到位置 i 时，首先找到下一个与 nums[i] 不同的数的位置 j。
    这表示从 i 到 j-1 都是相同的数。
  3. 决策1：这组相同的数一个都不要。直接从 j 位置继续递归。
  4. 决策2：依次决策要1个、2个…直到 j-i 个相同的数。
    每做一次选择，就将数加入路径，然后从 j 位置继续递归。

生成不同的组合

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
        主函数，初始化并调用递归函数
        """
        ans = []
        # 排序是关键，它使得相同的元素相邻，便于后续去重处理
        nums.sort()
        path = [0] * len(nums)
        self._f(nums, 0, path, 0, ans)
        return ans

    def _f(self, nums: List[int], i: int, path: List[int], size: int, ans: List[List[int]]):
        """
        递归函数，生成不重复的组合
        """
        # base case: 当 i 到达数组末尾时，形成一个组合
        if i == len(nums):
            ans.append(path[:size])
        else:
            # 找到下一个不同于 nums[i] 的元素的位置 j
            j = i + 1
            while j < len(nums) and nums[j] == nums[i]:
                j += 1
            
            # 决策1: 当前数 nums[i] 一个都不要
            self._f(nums, j, path, size, ans)
            
            # 决策2: 依次尝试要 1 个、2 个... k 个 nums[i]
            # 从这一段相同数字里，依次选择 1 个、2 个、…、(j-i) 个放入路径，然后递归从 j 开始，即处理下一组数去
            for k in range(i, j):
                path[size] = nums[k]
                size += 1
                # 每次选择后，都从下一个不同的数 j 开始继续递归
                self._f(nums, j, path, size, ans)

区别：set去重 vs 剪枝去重

  • 剪枝去重：当有相同的元素时，不进入递归，直接跳过，避免重复计算。（本题有用到这方面的考虑）
  • set去重：当有相同的元素时，会进入递归，但最终结果会去重。（但是题目1没有）

算法分析

  • 时间复杂度：O(2^n × n)，所有不重复组合数量≤2^n
  • 空间复杂度：O(2^n × n)
  • 核心技巧：排序 + 剪枝去重

题目三：返回没有重复值数组的全部排列

问题描述

没有重复项数字的全排列。

测试链接：https://leetcode.cn/problems/permutations/

核心思想

使用交换模型：

  1. 递归函数 _f(nums, i) 的任务是确定数组中第 i 个位置应该放哪个数。
  2. 我们可以从 i 到 len(nums)-1 的范围内选择一个数，将它与 nums[i] 交换，
    这样就确定了第 i 位。
  3. 然后递归调用 _f(nums, i+1) 去确定第 i+1 位。
  4. 当 i 到达数组末尾时，一个完整的排列就形成了。
  5. 递归返回后，必须将之前交换的元素换回来（回溯），以确保不影响其他分支的决策。

全排列（1）
全排列（2）

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        主函数，初始化并调用递归函数
        """
        ans = []
        self._f(nums, 0, ans)  # 复用了原数组做路径
        return ans

    def _f(self, nums: List[int], i: int, ans: List[List[int]]):
        """
        递归函数，生成全排列
        核心思想 (交换模型)
        """
        # base case: 当 i 到达数组长度时，一个完整的排列就形成了
        if i == len(nums):
            ans.append(nums[:])  # 将当前排列的副本加入结果列表
        else:
            # 尝试将 i 到 len(nums)-1 的每个数放到 i 位置上
            for j in range(i, len(nums)):
                # 将 nums[j] 换到当前要确定的 i 位置
                self._swap(nums, i, j)
                # 递归去确定下一个位置 i+1
                self._f(nums, i + 1, ans)
                # 回溯：将数组恢复原样，以便 for 循环下一次迭代能正确执行
                self._swap(nums, i, j)

    def _swap(self, nums: List[int], i: int, j: int):
        nums[i], nums[j] = nums[j], nums[i]

算法分析

  • 时间复杂度：O(n! × n)
  • 空间复杂度：O(n!)
  • 核心技巧：交换模型 + 回溯

题目四：返回可能有重复值数组的全部排列（去重）

问题描述

有重复项数组的去重全排列。

测试链接：https://leetcode.cn/problems/permutations-ii/

核心思想

核心思想 (在交换模型基础上增加剪枝逻辑)：
与生成无重复数字的全排列思路基本一致，但增加了一个去重机制。

  1. 在确定第 i 个位置的数时，我们遍历 j from i to len-1。
  2. 为了防止产生重复排列，我们规定：在第 i 个位置，一个数只能被放一次。
    例如，对于 [1, 2, 2]，在确定第0位时，我们尝试放第一个 2，
    就不应该再尝试放第二个 2，因为这两种情况后续会产生完全相同的排列。
  3. 使用一个集合 seen (或 set) 来记录在当前位置 i 已经尝试过的数字。
    如果 nums[j] 已经被放过，就跳过。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        主函数，初始化并调用递归函数
        """
        ans = []
        self._f(nums, 0, ans)
        return ans

    def _f(self, nums: List[int], i: int, ans: List[List[int]]):
        """
        递归函数，生成不重复的全排列
        在交换模型基础上增加剪枝逻辑
        """
        if i == len(nums):
            ans.append(nums[:])
        else:
            # seen 集合用于记录在当前 i 位置上已经尝试过的数字
            seen: Set[int] = set()
            for j in range(i, len(nums)):
                # nums[j]没有来到过i位置，才会去尝试
                if nums[j] not in seen:
                    # 记录下来，表示 nums[j] 这个值已经在 i 位置上用过了
                    seen.add(nums[j])
                    # 交换，将 nums[j] 放到 i 位置
                    self._swap(nums, i, j)
                    # 递归处理下一个位置
                    self._f(nums, i + 1, ans)
                    # 回溯，恢复数组
                    self._swap(nums, i, j)
                    
    def _swap(self, nums: List[int], i: int, j: int):
        nums[i], nums[j] = nums[j], nums[i]

算法分析

  • 时间复杂度：O(n! × n)
  • 空间复杂度：O(n!)
  • 核心技巧：交换模型 + 集合去重

题目五：用递归逆序一个栈

问题描述

用递归函数逆序栈，不能使用任何额外的数据结构。

核心思想

需要两个递归函数：

  1. bottom_out：移除并返回栈底元素，同时保持其他元素顺序不变
  2. reverse：利用bottom_out函数来逆序整个栈

逆序栈bottom_out方法
逆序栈reverse方法

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def reverse(self, stack: List[int]):
        """
        主递归函数，用于逆序整个栈。
        核心思想：
        1. 假设有一个函数 `_bottom_out` 可以移除并返回栈底元素。
        2. `reverse` 函数首先调用 `_bottom_out` 得到栈底元素 `num`。
        3. 然后，递归调用 `reverse` 来逆序剩下的 n-1 个元素的栈。
        4. 最后，将之前取出的栈底元素 `num` 压入已逆序的栈中，此时它就成了新的栈顶。
        """
        if not stack:
            return
        
        # 递归地移除并获取栈底元素
        num = self._bottom_out(stack)
        # 递归地逆序剩余的栈
        self.reverse(stack)
        # 将取出的栈底元素压入栈顶
        stack.append(num)

    def _bottom_out(self, stack: List[int]) -> int:
        """
        辅助递归函数，移除并返回栈底元素，同时保持其他元素顺序不变。
        核心思想：
        1. 弹出栈顶元素 `ans`。
        2. 如果栈空了，说明 `ans` 就是我们想要的栈底元素，返回它。
        3. 如果栈不空，递归调用 `_bottom_out` 获取剩下部分的栈底元素 `last`。
        4. 在递归返回的过程中，将之前弹出的 `ans` 重新压栈，以恢复栈的状态。
        5. 将从递归深处得到的 `last` 一路返回上去。
        """
        ans = stack.pop()
        if not stack:
            return ans  # 如果栈空了，说明ans就是栈底元素
        else:
            last = self._bottom_out(stack)  # 递归获取剩下部分的栈底元素
            stack.append(ans)  # 在递归返回过程中，将之前弹出的ans重新压栈
            return last  # 将从递归深处得到的last一路返回上去

执行过程示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
原栈: [1, 2, 3, 4, 5] (5在栈顶)

第1次reverse调用:
  bottom_out取出栈底1，栈变为[2, 3, 4, 5]
  递归reverse([2, 3, 4, 5])
  返回后将1压入栈顶

第2次reverse调用:
  bottom_out取出栈底2，栈变为[3, 4, 5]
  递归reverse([3, 4, 5])
  返回后将2压入栈顶

...以此类推

最终结果: [1, 2, 3, 4, 5] (1在栈顶)

算法分析

  • 时间复杂度：O(n²)
  • 空间复杂度：O(n) (递归栈空间)
  • 核心技巧：双递归函数配合

题目六：用递归排序一个栈

问题描述

用递归函数排序栈，只能使用栈提供的push、pop、isEmpty三个方法，以及递归函数。要求排完序后，从栈顶到栈底从小到大。

除此之外不能使用任何的容器，数组也不行。就是排序过程中只能用：(1) 栈提供的push、pop、isEmpty三个方法，(2) 递归函数，并且返回值最多为单个整数

核心思想

这是一个类似选择排序的递归实现。

  1. 整个排序过程分为 deep 轮，deep 是当前未排序部分的栈深度。
  2. 在每一轮中，目标是找出这 deep 个元素中的最大值（可能不止一个），并将它们“沉”到这 deep 个元素的最底部。
  3. _max() 函数：递归地在 deep 层中找到最大值。
  4. _times() 函数：递归地在 deep 层中统计这个最大值出现了几次 k。
  5. _down() 函数：递归地将这 k 个最大值移动到 deep 层的底部，同时保持其他 deep-k 个元素的相对顺序。
  6. 完成一轮后，未排序的深度减少 k (deep -= k)，然后对剩下的 deep 个元素重复此过程。

排列栈_整体框架
排列栈_deep方法
排列栈_max方法
排列栈_times方法
排列栈_down方法

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
    def sort_stack(self, stack: List[int]):
        deep = self._deep(stack)
        while deep > 0:
            # 找到当前 deep 范围内的最大值
            maximum = self._max(stack, deep)
            # 统计最大值出现的次数
            k = self._times(stack, deep, maximum)
            # 将这 k 个最大值沉底
            self._down(stack, deep, maximum, k)
            # 待排序的深度减少 k
            deep -= k

    def _deep(self, stack: List[int]) -> int:
        """返回栈的深度，不改变栈的数据状况"""
        if not stack:
            return 0
        num = stack.pop()
        deep = self._deep(stack) + 1
        stack.append(num)  # 恢复现场
        return deep

    def _max(self, stack: List[int], deep: int) -> int:
        """从栈当前的顶部开始，往下数deep层，返回这deep层里的最大值"""
        if deep == 0:
            return -float('inf')  # 返回一个极小值作为基准
        num = stack.pop()
        rest_max = self._max(stack, deep - 1)
        current_max = max(num, rest_max)
        stack.append(num)  # 恢复现场
        return current_max

    def _times(self, stack: List[int], deep: int, maximum: int) -> int:
        """返回maximum在deep层中出现的次数，不改变栈的数据状况"""
        if deep == 0:
            return 0
        num = stack.pop()
        rest_times = self._times(stack, deep - 1, maximum)
        times = rest_times + (1 if num == maximum else 0)
        stack.append(num)  # 恢复现场
        return times

    def _down(self, stack: List[int], deep: int, maximum: int, k: int):
        """将k个最大值沉到deep层的底部，剩下的数据状况不变"""
        if deep == 0:
            # 递归到底部时，先把k个最大值压入栈
            for _ in range(k):
                stack.append(maximum)
        else:
            num = stack.pop()
            self._down(stack, deep - 1, maximum, k)
            # 在递归返回时，只把非最大值的元素压回去
            if num != maximum:
                stack.append(num)

算法分析

  • 时间复杂度：O(n²)
  • 空间复杂度：O(n) (递归栈空间)
  • 核心技巧：多递归函数配合 + 选择排序思想

题目七：打印n层汉诺塔问题的最优移动轨迹

问题描述

打印n层汉诺塔问题的最优移动轨迹。

核心思想

这是一个经典的递归分治问题。要将 i 个盘子从 A 移动到 C：

  1. 先将 i-1 个盘子从 A 移动到 B (辅助柱)。
  2. 再将第 i 个盘子 (最大的那个) 从 A 移动到 C。
  3. 最后将 i-1 个盘子从 B 移动到 C。
    这个过程完美地将一个大问题分解为两个规模更小的相同问题和一个简单的单步操作。

汉诺塔问题描述
汉诺塔的最优移动轨迹
汉诺塔的抽象流程

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TowerOfHanoi:
    def hanoi(self, n: int):
        """
        汉诺塔问题主函数入口
        """
        if n > 0:
            self._f(n, "左", "右", "中")

    def _f(self, i: int, start: str, end: str, other: str):
        """
        递归函数，解决将 i 个圆盘从 start 移动到 end 的问题
        """
        # base case：如果只有一个圆盘，直接移动
        if i == 1:
            print(f"移动圆盘 1 从 {start} 到 {end}")
        else:
            # 步骤1: 将 i-1 个圆盘从 start 移动到 other
            self._f(i - 1, start, other, end)
            # 步骤2: 移动第 i 个圆盘从 start 到 end
            print(f"移动圆盘 {i} 从 {start} 到 {end}")
            # 步骤3: 将 i-1 个圆盘从 other 移动到 end
            self._f(i - 1, other, end, start)

执行过程示例（n=3）

1
2
3
4
5
6
7
8
解决 3 层汉诺塔问题的步骤：
移动圆盘 1 从 左 到 右
移动圆盘 2 从 左 到 中
移动圆盘 1 从 右 到 中
移动圆盘 3 从 左 到 右
移动圆盘 1 从 中 到 左
移动圆盘 2 从 中 到 右
移动圆盘 1 从 左 到 右

算法分析

  • 时间复杂度：O(2^n)
  • 空间复杂度：O(n) (递归栈空间)
  • 核心技巧：递归分治

递归技巧总结

1. 递归模板

1
2
3
4
5
6
7
8
9
10
11
12
def recursive_function(parameters):
    # base case: 递归终止条件
    if base_condition:
        return base_result
    
    # 递归调用：分解问题
    result = recursive_function(modified_parameters)
    
    # 处理当前层的逻辑
    current_result = process(result)
    
    return current_result

2. 回溯模板

1
2
3
4
5
6
7
8
9
10
11
12
def backtrack(path, choices):
    # base case
    if satisfied:
        result.append(path[:])  # 收集结果
        return
    
    for choice in choices:
        # 做选择
        path.append(choice)
        backtrack(path, remaining_choices)
        # 撤销选择
        path.pop()

3. 常见递归模式

选择模式

1
2
3
4
5
6
7
8
9
10
11
12
13
# 对每个元素有选择：要 or 不要
def choose(i, path):
    if i == len(arr):
        process(path)
        return
    
    # 要当前元素
    path.append(arr[i])
    choose(i + 1, path)
    path.pop()
    
    # 不要当前元素
    choose(i + 1, path)

交换模式

1
2
3
4
5
6
7
8
9
10
# 全排列问题
def permute(arr, i):
    if i == len(arr):
        process(arr)
        return
    
    for j in range(i, len(arr)):
        swap(arr, i, j)
        permute(arr, i + 1)
        swap(arr, i, j)  # 回溯

复杂度分析总结

题目 时间复杂度 空间复杂度 核心技巧
字符串子序列 O(2^n × n) O(2^n × n) 选择模式 + set去重
数组组合 O(2^n × n) O(2^n × n) 排序 + 剪枝去重
无重复全排列 O(n! × n) O(n!) 交换模式 + 回溯
有重复全排列 O(n! × n) O(n!) 交换模式 + 集合去重
递归逆序栈 O(n²) O(n) 双递归函数
递归排序栈 O(n²) O(n) 多递归函数
汉诺塔 O(2^n) O(n) 递归分治

学习建议

  1. 理解递归本质：递归就是函数调用自己，关键在于找到递归关系和base case

  2. 掌握常见模式：

    • 选择模式（子集、组合问题）
    • 交换模式（排列问题）
    • 分治模式（汉诺塔、归并排序等）

  3. 注意回溯时机：

    • 何时需要回溯（恢复现场）
    • 何时不需要回溯（使用额外空间）

  4. 优化技巧：

    • 剪枝去重 vs set去重
    • 空间复用（固定长度数组 + size指针）
    • 预处理（排序、哈希表等）

  5. 递归栈深度：注意递归深度，避免栈溢出

  6. 实践建议：

    • 多画递归树理解执行过程
    • 从简单案例开始推导
    • 注意边界条件的处理

递归是解决很多复杂问题的有力工具，掌握好递归的思想和常见模式，可以大大提升解决问题的能力。