算法面试题：递归与分治

1. 什么是递归？

• 函数调用自身。
• 需要基准条件终止。
• 常用于树、回溯、动态规划。

2. 分治算法的核心思想是什么？

• 将问题拆分为子问题。
• 分别求解子问题再合并结果。
• 如归并排序、快速排序。

3. 如何避免递归栈溢出？

• 控制递归深度。
• 改写为迭代。
• 使用尾递归优化（部分语言支持）。

4. 面试常问的递归题有哪些？

• 二叉树遍历。
• 全排列。
• 组合求和。
• 爬楼梯。

5. 递归题的复杂度如何分析？

• 用递推式表示时间复杂度。
• 使用主定理求解分治复杂度。

6. 什么时候应该改用动态规划？

• 存在重复子问题。
• 可以用状态压缩或记忆化递归优化。