算法基础

递归算法

递归算法是一种通过函数调用自身来解决问题的方法。它将复杂问题分解为相似的子问题，直到达到一个可以直接求解的简单情况（称为“基线条件”）。递归的核心思想是自我重复与逐层简化，常见于树结构遍历、分治算法等场景。

基础理论

在分析递归算法的时间复杂度之前，我们需要知道几个基础理论，递归的求解路线本质上是一个树结构，可以化为一个树结构来分析递归深度和调用次数：

对于深度为 $d$ 的 $k$ 叉树（ $d$ 从0开始， $k>1$ ），最多有 $k^{d+1}-1$ 个节点数量；
对于问题规模n，每次k分递归（比如，二分递归），得到的树的深度为 $log_kn$ （下文默认向下取整），深度为 $log_kn$ 的 $k$ 叉树，总节点数量 $m = k^{log_kn + 1} - 1=kn-1$ ，也就是线性近似于 $n$ ；
递归函数代码中，出现 $k$ 个自调用函数，对应的递归树就是 $k$ 叉树；

请注意，一般来说，一个节点对应一次递归调用，但是不同深度的节点对应的调用，时间复杂度不一定相同。

时间复杂度

我们写几个递归函数，来举例如何分析时间复杂度。

首先，网上很多方法都会提到这个公式：递归的时间复杂度 = 递归调用总次数 $\times$ 单次调用函数中的时间复杂度。

这个公式在不同深度的节点对应的调用的时间复杂度都一样的情况下，没有问题，但是如果单次调用函数中的时间复杂度不同，那就会出问题，比如说，这个公式解释不了为什么归并排序的时间复杂度是 $O(n~log_2n)$ 。

本质上，这个公式只是个特例，即每次调用函数的时间复杂度完全相同。作为一般化方法，这里给出递归的通用时间复杂度计算公式：

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} T(j)

其中 $D$ 为递归树的所有节点（即所有递归调用的集合）， $d_i$ 为深度为 $i$ 的所有节点（即第 $i$ 层树的所有节点的集合）， $T(j)$ 表示某个节点 $j$ 的时间复杂度。

这个公式的核心含义是：计算递归树所有节点的时间复杂度之和。

在实际分析中，我们遵循以下步骤：

出现了几个自调用函数？以决定递归树是几叉树；
递归树的深度是多少？
单次调用的复杂度是多少？
总时间复杂度是多少？

斐波那契数列

class Solution {
  public:
    int fib(int n) {
      if (n < 2) return n;
      return fib(n - 1) + fib(n - 2);
    }
};

这是斐波那契数列的递归算法实现，时间复杂度是多少呢？

首先看出现了几个自调用函数，显然是两个：fib(n-1), fib(n-2)，因此递归树是一个二叉树；
然后看递归树的深度，显然是 $n$ ；
所有节点对应的调用函数的时间复杂度都相同，均为 $O(1)$ ；

根据二叉树的性质，第 $i$ 层的节点数量为 $2^i$ ，根据公式求解：

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(1)=\sum_{i=0}^{n}2^iO(1)=O(1)\sum_{i=0}^{n}2^i\simeq O(2^n)

因此该算法的时间复杂度为 $O(2^n)$ 。

求x的n次方

int func1(int x, int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

求 $x^n$ ，当然这里只是循环，不是递归，由于只有一个for循环，因此时间复杂度就是 $O(n)$ 。

第一种递归算法：

int func1(int x, int n) {
    if (n == 0) {
        return 1;
    }
    return func1(x, n - 1) * x;
}

时间复杂度是多少呢？

首先看出现了几个自调用函数，显然是1个：func1(x, n-1)，因此递归树是一叉树（即链表结构）；
然后看递归树的深度，显然是 $n$ ；
单次调用函数中，时间复杂度为常数操作（一次乘法操作）。

一叉树，每层节点数量固定为1，列公式：

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(1)=\sum_{i=0}^{n}O(1)\simeq O(n)

因此该算法的时间复杂度为 $O(n)$ 。

这个复杂度是可以优化，比如：

int func2(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    if (n % 2 == 1) {
        return func2(x, n / 2) * func2(x, n / 2)*x;
    }
    return func2(x, n / 2) * func2(x, n / 2);
}

这个算法的时间复杂度是多少呢？

首先看出现了几个自调用函数，显然是两个：func2(x, n / 2)（调用了两次），因此递归树是二叉树；
然后看递归树的深度，根据前面提到的基础理论，对于二分递归，递归树深度为 $log_2n$ ；
单次调用函数中，时间复杂度为常数操作。

二叉树的性质，第 $i$ 层的节点数量为 $2^i$ （ $i$ 从0开始），故

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(1)=\sum_{i=0}^{log_2n}2^iO(1)=O(1)\sum_{i=0}^{log_2n}2^i= O(2n-1)

因此该算法的时间复杂度为 $O(2n-1) = O(n)$ 。

当然这里只是展示复杂度的计算过程，这个算法明显是可以把func2(x, n / 2)提取出来只算一次的：

int func3(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    int t = func3(x, n / 2);	// 提取出来，只需要算一次
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

此时的时间复杂度是多少呢？

首先看出现了几个自调用函数，显然是1个：func3(x, n / 2)（调用了两次），因此递归树是一叉树；
然后看递归树的深度，递归树深度为 $log_2n$ ；

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(1)=\sum_{i=0}^{log_2n}O(1)\simeq O(log_2n)

因此该算法的时间复杂度为 $O(log_2n)$ 。

对于幂运算，最优的时间复杂度就是 $O(log_2n)$ ，但是这个算法还是可以优化的，比如使用迭代代替递归，减少调用栈开销，用位运算代替等：

int func3_bit(int x, int n) {
    int result = 1;
    while (n > 0) {
        if (n & 1) {           // 代替 n % 2 == 1
            result *= x;
        }
        x *= x;
        n >>= 1;              // 代替 n /= 2
    }
    return result;
}

该算法的时间复杂度仍然为 $O(log_2n)$ （因为迭代次数为 $log_2n$ ）。

阶乘计算

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

出现了1次自调用，树结构为一叉树；
递归深度为 $n$ ；

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(1)=\sum_{i=0}^{n}O(1)\simeq O(n)

因此时间复杂度为： $O(n)$ 。

二分查找

int binarySearch(int arr[], int l, int r, int x) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) 
        return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
}

出现了1次自调用，树结构为一叉树；
递归深度为 $log_2n$ ；

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(1)=\sum_{i=0}^{log_2n}O(1)\simeq O(log_2n)

时间复杂度： $O(log_2n$ )。

归并排序

原理简单介绍一下：

第一步：分解（Divide）

原始数组：[8, 3, 2, 9, 7, 1, 5, 4]
        ↓ 递归分解
[8, 3, 2, 9]  [7, 1, 5, 4]
    ↓              ↓
[8, 3] [2, 9]  [7, 1] [5, 4]
  ↓      ↓       ↓      ↓
[8][3] [2][9]  [7][1] [5][4]

第二步：合并（Merge）

[8][3] → [3, 8]    // 比较合并
[2][9] → [2, 9]    // 比较合并
[3,8] + [2,9] → [2, 3, 8, 9]  // 有序合并

同理处理右半部分：
[7][1] → [1, 7]
[5][4] → [4, 5]
[1,7] + [4,5] → [1, 4, 5, 7]

最后合并：
[2,3,8,9] + [1,4,5,7] → [1,2,3,4,5,7,8,9]

归并排序的巧妙之处在于分治策略让"节点数增长"和"问题规模缩小"完美平衡，最终得到 $O(n ~log_2 n)$ 的高效算法。递归算法实现：

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, l, mid);      // T(n/2)
    mergeSort(arr, mid + 1, r);  // T(n/2)
    merge(arr, l, mid, r);       // O(n)
}

其中：

void merge(int arr[], int l, int mid, int r) {
    // 创建临时数组
    vector<int> temp(r - l + 1);
    int i = l, j = mid + 1, k = 0;
    // 比较两个有序子数组，选择较小的元素
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 复制剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    
    // 将临时数组复制回原数组
    for (int p = 0; p < k; p++) {
        arr[l + p] = temp[p];
    }
}

这里跟前面的算法不同的是，单次调用的函数体中，merge函数的复杂度为不再是 $O(1)$ ，分析如下：

自调用次数为两次，递归树为二叉树；
递归深度为 $log_2n$ ；
对于第 $i$ 层树，单次调用函数的时间复杂度为 $O(\dfrac{n}{2^i})$ （即跟深度 $i$ 和数据规模 $n$ 有关系）；

同样列公式：

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(\dfrac{n}{2^i})=\sum_{i=0}^{log_2n}2^iO(\dfrac{n}{2^i})=\sum_{i=0}^{log_2n}O(n)\simeq O(n ~log_2 n)

这是归并排序时间复杂度为 $O(n~log_2n)$ 的推导过程。

快速排序

来看看比较复杂的快速排序：

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // O(n)
        quickSort(arr, low, pi - 1);         // T(k)
        quickSort(arr, pi + 1, high);        // T(n-k-1)
    }
}

第一步：分区（Partition）

原始数组：[8, 3, 2, 9, 7, 1, 5, 4]
选择基准：4（最后一个元素）

第一次分区：
小于等于4的元素：[3, 2, 1, 4]
大于4的元素：[8, 9, 7, 5]
→ [3, 2, 1, 4, 8, 9, 7, 5]
基准位置：3（索引从0开始）

递归分区左半部分：[3, 2, 1]
选择基准：1
→ [1, 2, 3]

递归分区右半部分：[8, 9, 7, 5]
选择基准：5
→ [5, 9, 7, 8] → 继续分区

第二步：递归排序

左子树：[3, 2, 1]
    ↓ 基准：1
[1] + [3, 2]
        ↓ 基准：2
    [2, 3]
→ [1, 2, 3]

右子树：[8, 9, 7, 5]
    ↓ 基准：5
[5] + [8, 9, 7]
        ↓ 基准：7
    [7] + [8, 9]
            ↓ 基准：9
        [8, 9]
→ [5, 7, 8, 9]

第三步：最终结果

左子树结果：[1, 2, 3]
右子树结果：[5, 7, 8, 9]
基准元素：4

最终排序结果：[1, 2, 3, 4, 5, 7, 8, 9]

因此，partition(arr, low, high) 需要遍历一次元素集，时间复杂度为不再是 $O(1)$ ，继续分析：

自调用次数为2，递归树为二叉树；
递归树的深度，如果每次都均匀对半分区，那么深度为 $log_2n$ ，如果最差的情况，每次都以最大或者最小元素分区，那么深度接近 $n$ ，此时二叉树退化为链表结构（一叉树）；
单次调用时间复杂度，如果每次都均匀对半分区，复杂度为 $O(\dfrac{n}{2^i})$ （对于第 $i$ 层树），如果每次都以最大或者最小元素分区，复杂度接近 $O(n-i)$ ；

深度为 $log_2n$ 的情况：

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(\dfrac{n}{2^i})=\sum_{i=0}^{log_2n}2^iO(\dfrac{n}{2^i})=\sum_{i=0}^{log_2n}O(n)\simeq O(n ~log_2 n)

深度为 $n$ 的情况：

T(n) = \sum_{d_i\in D}\sum_{j\in d_i} O(n)=\sum_{i=0}^nO(n-i)\simeq O(n^2)

这是快速排序平均时间复杂度为 $O(n ~log_2 n)$ ，最差时间复杂度为 $O(n^2)$ 的推导过程。

二叉树遍历

void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);    // T(n₁)
    cout << root->val;
    inorder(root->right);   // T(n₂)
}

自调用次数为2，递归树为二叉树；
递归深度为 $n$ ；

对于这种简单的情形，没必要次次列公式推导，就计算树的所有节点的时间复杂度之和就行。

遍历二叉树的时间复杂度为 $O(n)$ 。

汉诺塔问题

汉诺塔（Tower of Hanoi）是一个经典的递归问题和数学谜题，由法国数学家爱德华·卢卡斯在1883年发明。

问题描述

游戏设置：

有3根柱子（A、B、C）
在柱子A上有n个大小不同的圆盘，按从上到下从小到大的顺序叠放
另外两根柱子B和C开始时为空

目标：
将所有圆盘从柱子A移动到柱子C

规则：

每次只能移动一个圆盘
移动时只能移动最上面的圆盘
大盘不能放在小盘上面

这个问题的递归解法思路为：

要将n个盘子从A移到C（借助B）：
1. 将n-1个盘子从A移到B（借助C）
2. 将最大的盘子从A移到C
3. 将n-1个盘子从B移到C（借助A）

代码：

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);    // T(n-1)
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, aux, to, from);    // T(n-1)
}

自调用次数为2，递归树结构为二叉树；
最大深度为 $n$ ；

计算树的所有节点的时间复杂度之和，时间复杂度为 $O(2^n)$ 。

习题

练习建议

画出递归树：对于每个算法，尝试画出递归调用的树状结构
计算递归深度：确定递归的最大深度
分析每层工作量：计算递归树每层的时间复杂度

数组求和

int arraySum(int arr[], int n) {
    if (n <= 0) return 0;
    return arr[n - 1] + arraySum(arr, n - 1);
}

时间复杂度分析：

单次递归调用
递归深度： $n$
时间复杂度： $O(n)$

二叉树高度计算

int treeHeight(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

时间复杂度分析：

每个节点访问一次
时间复杂度： $O(n)$ （ $n$ 为节点数）

全排列生成

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]); // 回溯
    }
}

时间复杂度分析：

递归深度： $n$
每层分支数递减： $n, n-1, n-2, ..., 1$
时间复杂度： $O(n!)$

子集生成

void subsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    if (index == nums.size()) {
        result.push_back(current);
        return;
    }
    // 不包含当前元素
    subsets(nums, index + 1, current, result);
    // 包含当前元素
    current.push_back(nums[index]);
    subsets(nums, index + 1, current, result);
    current.pop_back(); // 回溯
}

时间复杂度分析：

递归树为完全二叉树
递归深度： $n$
总节点数： $2^n$
时间复杂度： $O(2^n)$

快速幂计算

double power(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    
    double half = power(x, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

时间复杂度分析：

每次递归问题规模减半
递归深度： $log_2n$
时间复杂度： $O(log_2n)$

最大公约数（欧几里得算法）

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

时间复杂度分析：

每次递归参数至少减半
递归深度： $O(log_2(min(a,b)))$
时间复杂度： $O(log_2(min(a,b)))$