##递归

###递归的作用

• 替代多重循环
• 解决本来就是用递归定义的问题（比如斐波拉契数列）
• 将问题分解为更小的子问题来进行求解

###如何理解递归？

####N的阶层

N的阶层问题的递归调用栈可以简单表示如下（N=4）：

|   参数:0 |   1*f(0)  |  返回值：1  |
------------------------------------
|   参数:1 |   2*f(1)  |  返回值：1  |
------------------------------------
|   参数:2 |   3*f(2)  |  返回值：2  |
------------------------------------
|   参数:3 |   4*f(3)  |  返回值：6  |
------------------------------------
|   参数:4 |   f(4)    |  返回值：24 |
------------------------------------

往上每扩展一层代表一次函数调用 函数从调用栈的最底层开始执行，同时将当前层的参数和返回值存储在栈空间，然后逐层返回并弹出栈元素

###如何理解递归，回溯和分治的关系

####斐波拉契数列

递归树如下所示：

          f(4)
        /     \
     f(3)      f(2)
     /  \      /  \
  f(2)  f(1) f(1) f(0)
  /  \  
f(1) f(0) 

####回溯&递归

像斐波拉契数列这样本身就是用递归定义的问题，可以认为是最典型的递归，只需要按照递归公式进行推导即可，最后再按照递归栈的顺序逐级返回结果。 什么情况下涉及到回溯？ 比如在全排列问题中，我们除了要按深度优先遍历的方法遍历整递归树以外，每一次往下层递归的时候，还要知道当前那个数字被使用过，以免生成重复的数列。 因为涉及到节点状态，所以就出现了状态回溯，此时我们就需要在下一层递归之前使用一个局部变量存储需要的状态值，然后传入下一层递归，并在最后对状态进行清理。

####分治&递归

个人理解，分治是递归的一种优化方式，可以简单分为两种：

• 将简单的问题拆分的更加复杂，主要是为了优化
• 识别复杂问题的重复性，所以要拆分成更好理解的子问题，主要是为了方便编写代码

在 "计算 x 的 n 次幂函数" 的问题中，本身是一个很简单的数学问题，如果用暴力求解法是很容易理解的，但是性能极差，为了实现性能优化，我们需要将这个简单的问题分步骤进行实现，拆分成求当前数1/2的n次幂，最后将结果按照不同的情况进行组合。 在 "组合"这个问题中，我们需要识别问题的重复性，这个其实是有点困难的（至少对我），采用分治的思想，我们需要列举子问题来概括出重复性，这个问题的子问题包括：

• 不选择第N个数
• 选择第N个数

这样很容易理解，但是需要适应这种拆分的思路，增加练习时间应该可以很快适应

####一句话总结 递归是DFS的一种实现方式，回溯法是DFS过程中可以进行的可选操作