回溯

什么是递归

1. 递归是一种非常高效、简洁的编码技巧，比如DFS深度优先搜索、前中后序二叉树等都是使用递归。

2. 递归在代码中的表现方式是方法或者函数调用自身，调用的过程为递，返回为归。

3. 基本上，所有递归问题都可以用地推公式来表示。如：

   f(n) = f(n-1) + 1，其中f(1)=1

递归需要满足三个条件

1. 一个问题的解可以分解为几个子问题的解。

2. 这个问题和分解后的子问题，除了数据规模不同，求解思路完全一样。

3. 存在递归终止条件。

写递归代码的方法

1. 找到将大问题分解为小问题的规律。

2. 写出地推公式。

3. 找出终止条件。

4. 将递推公式和终止条件翻译成代码。

优势 vs 弊端

优势

1. 表达能力强，代码简洁

弊端

1. 堆栈溢出

   函数调用时，会将临时变量封装为栈帧压入内存，等函数执行完成返回时，才出栈。如果递归求解规模很大，调用层次很深，一直压入栈，就会有堆栈溢出风险。

   可以通过限制递归调用最大深度来解决这个问题。

2. 重复计算

   可以通过一个数据结构来保存已经求解过的f(K)，从而避免重复计算。

3. 空间复杂度较高

4. 函数调用耗时较多

递归代码改为非递归代码

递归代码都可以改为迭代循环的非递归写法。