递归与迭代。

参考文献

递归详解

递归算法讲解

递归算法的理解

递归的本质

由于递归与迭代的特殊性。在这里单独列出一种思想。递归与迭代思想，用来处理所有的重复的操作。如分治法的相同子操作、动态规划的相同子操作、深度优先搜索、广度优先搜索的相同子操作。

1 递归法概述

基本思想

直接或间接的调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。
递归的数学模型其实就是数学归纳法。可以用反向递推式表示递归的过程。（使用正向递推式表示循环的过程）

线性收缩递归算法

递推关系式

$$
T(n)=\begin{cases}
o(1) & n=1 \
\sum_{i=1}^k a_iT(n-i)+f(n) & n>1
\end{cases}
$$

求解递推关系式
$$
T(n)=a^{n-1}T(1)+\sum_{i=2}^na^{n-i}f(i)
$$
关系式说明

等比收缩递归算法

递推关系式
$$
T(n)=\begin{cases}
O(1)&n=1 \
aT(\frac{n}{b})+f(n) & n>1
\end{cases}
$$
求解递推关系式
$$
T(n)=n^{\log_ba} +\sum_{i=2}^{\log_bn-1}a^jf(n/b^j)
$$
关系式说明

$$
T(n)=O(n^{\log_ba})+O(f(n))\log_bn
$$

其真正的时间复杂度，由前后两部分决定。可以通过计算，得到较大部分的时间复杂度，为整体的时间复杂度。
当f(n)为常数时
$$
T(n)=\begin{cases}
O(n^{\log_ba}) & a\not = 1\
O(\log n) & a=1
\end{cases}
$$
当f(n)=cn时

$$
T(n)=\begin{cases}
O(n)&a<b\
O(n\log n)& a=b\
O(n^{log_b^a})&a>b
\end{cases}
$$

递归的空间复杂度

当递归过深时，栈空间会被耗尽，这时就无法开辟新的函数，会报出stack overflow这样的错误。
所以，在考虑空间复杂度时，递归函数的深度也是要考虑进去的。

2 递归的分类

直接递归和间接递归

直接递归，是指函数自己调用自己的情况。
间接递归，是指调用其他函数时，在其他函数中又调用了自己的情况。

头递归和尾递归

头递归：递归发生在函数的其他处理代码之前（或理解为，递归发生在函数的头部或顶部）。需要先解决后续问题，上层依赖下层，最顶层得到结果，直接返回。
- 需要使用后续递归后的结果，参与本层的计算，然后返回给上一层。这时，需要在下层的递归完成后，才能计算。如归并计算，需要下一层拍好顺序，这一次才会执行归并操作。
尾递归：递归发生在函数其他处理代码的后面（或理解为，递归发生在函数的尾部）。需要先解决当前问题，下层依赖上层，最底层得到结果，返回顶层。
- 本层内的计算是为了确定递归过程中的条件。且下一层返回的结果，能够作为本层的结果返回。本层不知道改成的结果，结果取决于最底层。如搜索树的最大深度，只有递归到叶节点才知道最大深度是多少。快排也是，先解决本层的分割排序，在解决下一层的。
中间部分递归：递归发生在函数体的中间部分。
- 头递归和尾递归只是描述递归发生的相对顺序。实际上在递归过程中，递归可以发生在任何位置。递归前的代码负责处理本层的与下一层无关的内容。递归后的代码负责利用下一层的返回值或其他变量处理内容。

单分支递归和多分支递归

单分支递归：每一层只是常数级别缩小问题的规模。进行一次递归处理下一个问题。每一层只调用一次递归函数。如阶乘问题青蛙跳问题等。单分支递归往往能写成循环的形式，如二分法的递归和循环都可以。
多分支递归：当一个问题可以分为多个相同的子问题的时候。在同一层进行多分支递归。每一层多次调用递归函数。如树和图的遍历问题，有多个下层子节点。

3 递归的实现

递归问题的分析

提取重复的逻辑，缩小问题规模。
只有写出反向递推关系式，才知道递归的参数、递归的返回值和递归的执行关系。

递归算法的步骤

设计递归的参数。首先确定每一次递归，上一层需要提供给下一层的内容。相当于上层—->下层的接口。
设计递归的返回值。设计递归需要返回的内容，即提供给上一层的内容。相当于下层—->上层的接口。
设计递归的执行。找出函数的等价关系式。设计如何开始递归。怎样调用递归。有了上一层的参数和返回值的需求，相当于提供了一个函数的接口。那么就可以调用递归函数，开始递归了。
设计递归的终止条件。一旦开始递归，就要设计递归的终止条件。
递归前的数据处理。在递归前需要处理的数据，提供给递归函数。
递归后的数据处理。在递归后需要处理的数据。提供给上层函数和最终结果。

有一种特殊的递归处理方式。在递归前修改标志位。在递归后。将标志位还原。因为递归本质上是深度优先。所以，这个标志位只会影响一条路径上的问题。

递归的终止条件

终止递归：终止递归有两种思路。
1. 本层不满足条件。终止递归。当进入本层后，首先判断递归是否终止。
2. 下一层不满足条件。终止递归。当要进行递归前，判断是否还需要进行递归。前提是直到下一层是否满足条件的计算。
本层判断更符合递归的思想，且在实现过程中，也相对简单。

递归算法理解

递归算法本质上是一种自顶向下的思考模式。即数学上所说的归纳法。有结果一步一步归纳，得到验证其条件的正确性。问题规模逐渐变小。
非递归算法的本质是一种自底向上的思考模式。即数学上所说的推导法。将一些零碎的部分逐渐求解，渐渐得到最终的结果。问题逐渐组装成目标问题。
在使用递归的时候，应该从顶层考虑怎么分割。在使用非递归算法的时候，应该考虑怎样从底层进行组合。

4 迭代法概述

概念

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。
循环其实和递归具有相同的特性，即做重复任务。

5 迭代法的时间复杂度

取决于迭代嵌套的数量。每一层迭代为常数级别则：

$$
O(mn…*k)(m,n,k表示嵌套迭代的复杂度)\
O(m+n+…+k)(m,n,k表示并列迭代的复杂度)
$$

6 迭代法实现

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。在使用迭代算法解决问题时，需要做好如下3个方面的工作。
1. 确定迭代变量
2. 建立迭代关系
3. 控制迭代过程

6.1 确定迭代变量

在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。

6.2 建立迭代关系式

迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。

6.3 控制迭代过程

在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：
- 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；
- 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。

7 递归与迭代的区别与联系

二者都能处理重复的逻辑。降低算法的复杂度。
二者都能够使用递推关系式表示。迭代使用正向递推关系式，在数学上称为推导法，从最初的已知条件逐渐推导出自己想要的结果。递归使用反向递推关系式，在数学上称为归纳法，从结果触发，逐渐寻找满足计算的初始条件。
递归能够直接处理多个分支的问题（多分支递归）。循环需要借助特殊的数据结构保存另一个分支的状态，解决多分支问题。如堆栈和队列可以用来实现深搜广搜过程中保存其他分支。