解决递归问题的六种方法

许多软件工程师在编程面试中遇到递归问题。 如果你想成为善于解决递归问题，学习这6个模板：

1.迭代
任何可以用循环解决的问题也可以用递归解决。

有时候递归提供了一个更简洁和优雅的解决方案，即使效率较低。

范例：
- 按逆序遍历链表 

2.子问题
此模式侧重于定义和解决问题的较小版本。

标准的策略是从输入中删除一些内容。

示例如下：

• - 查找字符串是否为回文
• - 找到所有爬楼梯的方法 

3.选择
有些问题可以通过以下方式解决：

• ·查找某些输入元素的所有组合
• ·选择与给定条件匹配的组合

范例：
- 找到所有可能的方法来交错2字符串 

4.顺序
此模式类似于选择，但元素组合的顺序很重要。

这些问题可以通过以下方式解决：

• ·找到所有的排列
• ·过滤它们

范例：
- 找到所有的N位数的数字总和为一个目标数 

5.分而治之
此模式侧重于将问题拆分为多个子问题：

• ·每个子问题单独解决
• ·组合解决方案以获得结果

范例：
- 找到所有的方法来括号一个表达式

6.深度优先搜索
此模式在树或图中查找路径：

• ·从一个节点开始
• ·递归访问每个节点的邻居
• ·避免重复循环

范例：
- 在一个矩阵中从左上角到右下角找出乘积最大的路径