L5_06 递归算法

一、递归算法概述

递归是一种编程技巧，指函数在其定义中调用自身的过程。递归算法将复杂问题分解为更小的、相似的子问题，直到子问题足够简单，可以直接求解。

1.1 递归的基本结构

返回类型 函数名(参数) {
    // 基本情况（递归终止条件）
    if (基本条件) {
        return 基础值;
    }
    
    // 递归情况（调用自身）
    return 函数名(更小的参数);
}

1.2 递归的特点

• 优点：

  • 代码简洁，逻辑清晰
  • 易于理解和实现
  • 适合解决分治问题

• 缺点：

  • 可能导致栈溢出
  • 时间和空间复杂度较高
  • 可能存在重复计算

---

二、递归的经典示例

2.1 阶乘计算

int factorial(int n) {
    // 基本情况
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // 递归情况
    return n * factorial(n - 1);
}

执行过程：

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1
             = 120

2.2 斐波那契数列

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

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

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

---

三、递归的时间和空间复杂度

3.1 时间复杂度分析

递归的时间复杂度通常通过递归树来分析。对于一个递归函数，如果每次调用会产生 k 个子问题，且递归深度为 n，则时间复杂度为 O(k^n)。

3.2 空间复杂度分析

递归的空间复杂度主要由调用栈的深度决定。如果递归深度为 n，每个栈帧占用 O(1) 的空间，则空间复杂度为 O(n)。

3.3 示例分析

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

时间复杂度：O(2^n) - 指数级 空间复杂度：O(n) - 线性级（递归栈深度）

---

四、递归的优化策略

4.1 记忆化搜索

通过存储已经计算过的结果，避免重复计算。

int memo[1000];

int fibonacciMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    
    memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
    return memo[n];
}

优化后的时间复杂度：O(n)

4.2 动态规划

将递归转换为迭代，使用数组存储中间结果。

int fibonacciDP(int n) {
    if (n <= 1) return n;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

4.3 尾递归优化

尾递归是指递归调用是函数的最后一个操作。某些编译器可以对尾递归进行优化，将其转换为迭代。

int factorialTail(int n, int accumulator) {
    if (n == 0) return accumulator;
    return factorialTail(n - 1, n * accumulator);
}

int factorial(int n) {
    return factorialTail(n, 1);
}

---

五、递归的应用场景

5.1 树的遍历

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

5.2 图的深度优先搜索

void dfs(int node, vector<bool>& visited, const vector<vector<int>>& graph) {
    visited[node] = true;
    cout << node << " ";
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

5.3 排列组合

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]);  // 回溯
    }
}

---

六、递归与分治

分治算法通常采用递归实现：

1. 分解：将问题分解为若干个规模较小的子问题
2. 解决：递归地解决每个子问题
3. 合并：将子问题的解合并为原问题的解

int divideAndConquer(vector<int>& arr, int left, int right) {
    if (left == right) {
        return arr[left];
    }
    
    int mid = left + (right - left) / 2;
    int leftResult = divideAndConquer(arr, left, mid);
    int rightResult = divideAndConquer(arr, mid + 1, right);
    
    return combine(leftResult, rightResult);
}

---

七、递归的注意事项

1. 必须有终止条件：否则会导致无限递归，栈溢出
2. 避免重复计算：使用记忆化或动态规划优化
3. 注意栈溢出风险：递归深度不宜过大
4. 考虑尾递归优化：某些语言和编译器支持尾递归优化

---

八、总结

递归是一种强大的编程技巧，能够将复杂问题简化为相似的子问题。掌握递归思想对于学习分治、动态规划等高级算法至关重要。