递归算法基础

1. 递归的应用场景

• 数学计算问题：
  • 阶乘计算
  • 斐波那契数列
  • 组合数计算
• 数据结构操作：
  • 树的遍历
  • 链表操作
  • 图的搜索
• 分治问题：
  • 归并排序
  • 快速排序
  • 二分查找

6.1 汉诺塔问题：问题分析

问题描述：

• 有三根柱子A、B、C，A柱上有n个盘子
• 盘子大小递减排列，大盘不能放在小盘上
• 目标：将所有盘子从A移到C
• 每次只能移动一个盘子

递归分析：

1. 基本思路

   • 将问题分解为移动较少盘子的子问题
   • 利用辅助柱子作为中转
   • 保持大盘在小盘下方的约束

2. 递归过程

   graph TD
   A[移动n个盘子] --> B[移动n-1个盘子到辅助柱]
   B --> C[移动第n个盘子到目标柱]
   C --> D[移动n-1个盘子到目标柱]
   

3. 复杂度分析

   • 时间复杂度：O(2^n)
   • 空间复杂度：O(n)，递归栈深度
   • 移动次数：2^n - 1

4. 关键步骤

   • 将n-1个盘子从源柱移到辅助柱
   • 将第n个盘子从源柱移到目标柱
   • 将n-1个盘子从辅助柱移到目标柱

6.1 汉诺塔问题：代码实现

/**
 * 汉诺塔递归求解函数
 * @param n: 要移动的盘子数量
 * @param from: 源柱子
 * @param aux: 辅助柱子
 * @param to: 目标柱子
 */
void hanoi(int n, char from, char aux, char to) {
    // 基本情况：只有一个盘子时直接移动
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    
    // 递归步骤1：将n-1个盘子从源柱移到辅助柱
    hanoi(n - 1, from, to, aux);
    
    // 步骤2：将第n个盘子从源柱移到目标柱
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    
    // 递归步骤3：将n-1个盘子从辅助柱移到目标柱
    hanoi(n - 1, aux, from, to);
}

// 使用示例
int main() {
    int n = 3;  // 盘子数量
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

6.2 归并排序：问题分析

问题描述：

• 输入：一个无序数组
• 输出：按升序排列的有序数组
• 要求：使用分治策略实现排序

分治策略分析：

1. 基本思路

   • 将数组分成两个子数组
   • 递归排序子数组
   • 合并已排序的子数组

2. 递归过程

   graph TD
   A[原始数组] --> B[左半部分]
   A --> C[右半部分]
   B --> D[左左]
   B --> E[左右]
   C --> F[右左]
   C --> G[右右]
   D --> H[合并左半]
   E --> H
   F --> I[合并右半]
   G --> I
   H --> J[最终合并]
   I --> J
   

3. 复杂度分析

   • 时间复杂度：O(n log n)
   • 空间复杂度：O(n)
   • 分解次数：log n
   • 每层合并：O(n)

4. 优点与特性

   • 稳定排序算法
   • 适合大规模数据
   • 可并行化实现

6.2 归并排序：代码实现

/**
 * 合并两个已排序的子数组
 * @param arr: 原数组
 * @param left: 左边界
 * @param mid: 中间位置
 * @param right: 右边界
 */
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);  // 临时数组
    int i = left, j = mid + 1, k = 0;
    
    // 合并两个有序数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 处理剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    // 将临时数组复制回原数组
    for (i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

/**
 * 归并排序主函数
 * @param arr: 待排序数组
 * @param left: 左边界
 * @param right: 右边界
 */
void mergeSort(vector<int>& arr, int left, int right) {
    // 基本情况：数组长度为1或0
    if (left >= right) return;
    
    // 计算中间位置
    int mid = left + (right - left) / 2;
    
    // 递归排序左半部分
    mergeSort(arr, left, mid);
    // 递归排序右半部分
    mergeSort(arr, mid + 1, right);
    
    // 合并已排序的子数组
    merge(arr, left, mid, right);
}

// 使用示例
int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    mergeSort(arr, 0, arr.size() - 1);
    
    cout << "Sorted array: ";
    for(int num : arr) cout << num << " ";
    return 0;
}

6.3 组合生成：问题分析

问题描述：

• 输入：两个整数n和k
• 输出：所有可能的k个数的组合
• 范围：数字从1到n
• 要求：不能有重复组合，顺序无关

递归回溯分析：

1. 基本思路

   • 使用递归回溯法
   • 每个位置可以选择或不选择当前数字
   • 维护当前已选数字的集合
   • 当选择数量达到k时记录结果

2. 递归树结构

   graph TD
   A[开始] --> B[选择1]
   A --> C[不选1]
   B --> D[选择2]
   B --> E[不选2]
   C --> F[选择2]
   C --> G[不选2]
   D --> H[...]
   E --> I[...]
   F --> J[...]
   G --> K[...]
   

3. 优化策略

   • 剪枝：提前判断剩余数字是否足够
   • 空间优化：使用引用传递避免复制
   • 时间优化：合理设置起始位置

4. 复杂度分析

   • 时间复杂度：O(C(n,k))
   • 空间复杂度：O(k)，递归栈深度

6.3 组合生成：代码实现

/**
 * 生成组合的主函数
 * @param n: 数字范围上限
 * @param k: 要选择的数字个数
 * @return: 所有可能的组合
 */
vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;  // 存储所有组合
    vector<int> current;         // 当前组合
    
    // 调用辅助函数进行递归生成
    combineDFS(n, k, 1, current, result);
    return result;
}

/**
 * 递归生成组合的辅助函数
 * @param n: 数字范围上限
 * @param k: 要选择的数字个数
 * @param start: 当前可选的起始数字
 * @param current: 当前已选数字集合
 * @param result: 存储所有组合的结果集
 */
void combineDFS(int n, int k, int start, 
                vector<int>& current, 
                vector<vector<int>>& result) {
    // 基本情况：找到一个合法组合
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    
    // 优化1：剪枝
    // 如果剩余数字不够凑成k个，直接返回
    if (current.size() + (n - start + 1) < k) return;
    
    // 递归生成组合
    for (int i = start; i <= n; i++) {
        // 选择当前数字
        current.push_back(i);
        
        // 递归生成剩余位置的组合
        combineDFS(n, k, i + 1, current, result);
        
        // 回溯：撤销选择
        current.pop_back();
    }
}

// 使用示例
int main() {
    int n = 4, k = 2;
    vector<vector<int>> combinations = combine(n, k);
    
    cout << "All combinations of " << k << " numbers from 1 to " << n << ":\n";
    for (const auto& comb : combinations) {
        cout << "{ ";
        for (int num : comb) cout << num << " ";
        cout << "}\n";
    }
    return 0;
}

6.4 表达式求值：问题分析

问题描述：

• 输入：包含数字和运算符的字符串表达式
• 支持：加减乘除运算和括号
• 输出：表达式的计算结果
• 要求：正确处理运算符优先级

递归下降分析：

1. 基本原理

   • 将表达式分解为语法单元
   • 按照运算符优先级构建递归结构
   • 自顶向下分析表达式

2. 语法树结构

   graph TD
   A[表达式] --> B[项]
   A --> C[+ -]
   A --> D[项]
   B --> E[因子]
   B --> F[* /]
   B --> G[因子]
   E --> H[数字/括号]
   G --> I[数字/括号]
   

3. 优先级处理

   • 第一级：括号 ()
   • 第二级：乘除 * /
   • 第三级：加减 + -

4. 实现策略

   • 递归处理不同优先级
   • 使用辅助函数分解任务
   • 错误处理和边界检查

6.4 表达式求值：代码实现

/**
 * 表达式计算器类
 * 使用递归下降法解析和计算数学表达式
 */
class ExpressionEvaluator {
private:
    string expr;    // 存储表达式
    int pos = 0;    // 当前处理位置
    
    /**
     * 跳过空白字符
     */
    void skipSpace() {
        while (pos < expr.length() && expr[pos] == ' ') pos++;
    }
    
    /**
     * 解析表达式（处理加减法）
     * @return 表达式的计算结果
     */
    int parseExpr() {
        int left = parseTerm();  // 先获取第一项
        
        while (pos < expr.length()) {
            skipSpace();
            if (pos >= expr.length()) break;
            
            char op = expr[pos];
            if (op != '+' && op != '-') break;
            
            pos++;  // 跳过运算符
            int right = parseTerm();
            
            // 执行加减运算
            if (op == '+') left += right;
            else left -= right;
        }
        
        return left;
    }
    
    /**
     * 解析项（处理乘除法）
     * @return 项的计算结果
     */
    int parseTerm() {
        int left = parseFactor();  // 先获取第一个因子
        
        while (pos < expr.length()) {
            skipSpace();
            if (pos >= expr.length()) break;
            
            char op = expr[pos];
            if (op != '*' && op != '/') break;
            
            pos++;  // 跳过运算符
            int right = parseFactor();
            
            // 执行乘除运算
            if (op == '*') left *= right;
            else {
                if (right == 0) throw runtime_error("Division by zero");
                left /= right;
            }
        }
        
        return left;
    }
    
    /**
     * 解析因子（处理数字和括号）
     * @return 因子的值
     */
    int parseFactor() {
        skipSpace();
        
        // 处理括号表达式
        if (expr[pos] == '(') {
            pos++;  // 跳过左括号
            int val = parseExpr();
            skipSpace();
            if (pos >= expr.length() || expr[pos] != ')') 
                throw runtime_error("Missing closing parenthesis");
            pos++;  // 跳过右括号
            return val;
        }
        
        // 处理数字
        if (!isdigit(expr[pos]))
            throw runtime_error("Invalid character: " + string(1, expr[pos]));
            
        int val = 0;
        while (pos < expr.length() && isdigit(expr[pos])) {
            val = val * 10 + (expr[pos] - '0');
            pos++;
        }
        
        return val;
    }
    
public:
    /**
     * 构造函数
     * @param s 要计算的表达式
     */
    ExpressionEvaluator(string s) : expr(s) {}
    
    /**
     * 计算表达式的值
     * @return 表达式的计算结果
     */
    int evaluate() {
        pos = 0;  // 重置位置
        int result = parseExpr();
        skipSpace();
        if (pos < expr.length())
            throw runtime_error("Invalid expression");
        return result;
    }
};

// 使用示例
int main() {
    string expr = "2 * (3 + 4) * 5";
    ExpressionEvaluator eval(expr);
    
    try {
        cout << "Expression: " << expr << endl;
        cout << "Result: " << eval.evaluate() << endl;
    } catch (const exception& e) {
        cout << "Error: " << e.what() << endl;
    }
    
    return 0;
}

7. 总结

• 递归是一种重要的算法设计方法，通过将问题分解为相似的子问题来解决复杂问题
• 掌握递归的核心思想：基本情况、递归关系、问题分解
• 理解不同类型的递归：线性递归、树形递归、尾递归、互递归
• 熟练运用优化技巧，提高递归效率
• 递归与其他算法思想（如分治、动态规划）的结合，可以解决更复杂的问题