登录以参加训练计划

好的！递归算法就像俄罗斯套娃，大问题里包含着小问题，而小问题的解决方法和大问题一样~ 🪆 下面用超多图解+生活化例子帮你轻松掌握这个重要算法！

---

🌟 递归的核心思想

1. 自己调用自己：函数在执行过程中调用自身
2. 问题分解：把大问题分解成更小的同类问题
3. 终止条件：必须有个明确的结束条件（否则无限循环！）

---

🆚 递归 vs 递推

	递归	递推
方向	自顶向下（分解问题）	自底向上（迭代）
实现	函数调用自身	循环
效率	较低（可能有重复计算）	较高

---

✅ 递归三要素

1. 终止条件：什么时候不再递归？
2. 递归调用：如何缩小问题规模？
3. 问题分解：如何将大问题转化为小问题？

---

📚 经典递归问题

1. 阶乘计算

int factorial(int n) {
    if(n == 0) return 1;       // 终止条件
    else return n * factorial(n-1); // 递归调用
}

执行过程（以fact(3)为例）：

fact(3)
3 * fact(2)
3 * (2 * fact(1))
3 * (2 * (1 * fact(0)))
3 * (2 * (1 * 1)) = 6

---

2. 斐波那契数列

int fib(int n) {
    if(n <= 1) return n;                // 终止条件
    else return fib(n-1) + fib(n-2);    // 递归调用
}

⚠️ 注意：这种实现有大量重复计算，时间复杂度O(2^n)！

---

3. 汉诺塔问题

问题：将n个盘子从A柱移到C柱，每次只能移动一个，且大盘不能在小盘上

void hanoi(int n, char A, char B, char C) {
    if(n == 1) {
        cout << A << "->" << C << endl;
        return;
    }
    hanoi(n-1, A, C, B);  // 把n-1个从A移到B（借助C）
    cout << A << "->" << C << endl;
    hanoi(n-1, B, A, C);  // 把n-1个从B移到C（借助A）
}
// 调用：hanoi(3, 'A', 'B', 'C');

---

4. 二叉树遍历

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

void preOrder(TreeNode* root) {
    if(root == nullptr) return; // 终止条件
    cout << root->val << " ";   // 先访问根
    preOrder(root->left);       // 递归左子树
    preOrder(root->right);      // 递归右子树
}

---

💡 递归的应用场景

1. 树/图遍历：二叉树、文件目录结构
2. 分治算法：归并排序、快速排序
3. 数学问题：组合数、汉诺塔
4. 动态规划：递归+记忆化搜索

---

❗ 递归注意事项

1. 栈溢出风险：递归深度太大会导致栈溢出
2. 重复计算：如斐波那契的朴素递归实现
3. 效率优化：可用记忆化搜索（Memoization）或改写成迭代

---

🚀 递归优化技巧

1. 记忆化搜索（斐波那契优化）

int memo[100] = {0};

int fib(int n) {
    if(n <= 1) return n;
    if(memo[n] != 0) return memo[n]; // 已经计算过
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n;
}

2. 尾递归优化（阶乘优化）

int factorial(int n, int result = 1) {
    if(n == 0) return result;
    return factorial(n-1, n * result); // 尾调用，编译器可优化
}

---

🌰 生活化案例：家族族谱

假设你要统计家族成员数量：

1. 你的成员数 = 1（自己） + 所有孩子的成员数之和
2. 终止条件：没有孩子的人成员数就是1

int familyMembers(Person* person) {
    if(person == nullptr) return 0;
    int count = 1; // 自己
    for(auto child : person->children) {
        count += familyMembers(child);
    }
    return count;
}

---

📝 练习题

1. 反转字符串
   用递归实现：输入"hello"，输出"olleh"

   void reverse(string& s, int left, int right) {
       if(left >= right) return;
       swap(s[left], s[right]);
       reverse(s, left+1, right-1);
   }
   

2. 数组求和
   递归计算数组元素和

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

3. 判断回文串
   递归判断字符串是否为回文

   bool isPalindrome(string s, int left, int right) {
       if(left >= right) return true;
       if(s[left] != s[right]) return false;
       return isPalindrome(s, left+1, right-1);
   }
   

---

💡 理解递归的秘诀

1. 画调用树：用纸笔画出函数调用过程
2. 信任递归：只需关注当前层和终止条件，不要陷入调用细节
3. 调试技巧：在递归入口和出口打印变量值