递归与分治
掌握递归、分治思想及其高频应用
80%
🔄 递归思想与写法
🪓 分治算法与典型问题
🌟 经典例题与完整解答
💡 练习题与参考答案
递归思想与写法
递归是函数直接或间接调用自身，常用于分解重复子问题。递归与迭代的区别在于递归用栈保存状态，迭代用循环。递归模板：
// 递归模板
void recur(参数) {
if (终止条件) return;
// 处理当前层逻辑
recur(子问题参数);
// （可选）回溯清理
}示例：斐波那契数列（递归与迭代）
// 递归写法
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// 迭代写法
int fibIter(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
int c = a + b;
a = b; b = c;
}
return b;
}