1. 循环
循环，就是程序不断重复执行循环体，直到满足终止条件后，程序中断退出。循环本质是一种顺序的思想。
循环的一般格式为
每次循环都要进行一次操作
def func(): while True: operate() if status(): break change_status()可以转换为下列格式
def func(): operate() while status(): change_status() operate()判断两个循环是否等价，只要判断其循环体调用情况就可以了。
可以看出上面的循环都是
operate() -> status() -> (change_status() * (n-1) + operate()) -> status()，所以两者是等价的。特别地，两者的
status()是互斥的，例如，前者的判断条件为i < n，后者的判断条件应为i >= n，下面加粗的转换也有同样的规律。循环结束后再进行操作
def func(): while status(): change_status() operate()可以转换为下列格式
def func(): while True: if status(): operate() break change_status()
2. 递归
递归，就是程序可以不断调用自身，直到满足一定终止条件，程序中断返回上一层递归体，直到所有的递归体都返回结束，程序结束。递归本质是一种倒序的思想。
在20世纪50年代，当时最早的编程语言Fortran，是不允许程序调用自身的，也就是不允许递归。直到1960年，荷兰计算机学家 Edsger Wybe Dijkstra 在他的著作《递归编程》（Recursive Programming）中才首次提出了递归这一思想，其发明的ALGOL60也是最早支持递归的高级编程语言。
递归的思想应用了栈（stack）。在递归的时候，要先创建一个临时的内存空间，把当前运行的程序暂时封存在这一块内存空间中（入栈），然后去执行其调用的程序，知道其调用的程序执行完毕时，才把当前运行的程序解封（出栈），继续往下执行。
Dijkstra 当时就提出了逆波兰记法（Reverse Polish notation，RPN）来实现递归调用子程序时出栈入栈的环境维护。因为其算法把所有操作符置于操作数的后面，因此也被称为后缀表示法。
举个例子：
3 - (4 + 5) × 6 这个式子，可以表示为：3 4 5 + 6 × -
其运算过程为：
- 3、4、5正常入栈，然后输入操作符
+，4、5出栈进行运算，得到9；- 9入栈，6入栈，然后输入操作符
×，9、6出栈进行运算，得到54；- 54入栈，最后输入操作符
-，3、54 出栈运算，最后得到结果 -51.更加具体的说明可以参考这里
2.1. 递归表达式
递归表达式（状态转移方程）的标准形式为 \[ F(n) = G(n, n-1,n-2,...,n-i) + f(n, n-1, n-2, ..., n-j) \] 其中， \(G(\vec N) = G(n, n-1,n-2,...,n-i)\) 是一个关于 \(F(n)\) 的递归体函数， \(f(\vec N) = f(n, n-1, n-2, ..., n-j)\) 是一个关于 \(n\) 的增量函数，其伪函数表示为 \[ G(\vec N) = \text{multi-recursive}(\vec N) \\ f(\vec N) = \text{operate}(\vec N) \] 例如这就是一个典型的递归函数 \(F(n) = 2 F(n-1) + 3F(n-2) + 2 n + 1\)
理论上，对于所有的递归，都能总结出一条表达式，但归纳出怎样的表达式，是递归一类问题的难点。只要能得到递归表达式，后面只需要套格式就可以了，很多问题都能迎刃而解。
2.2. 单向递归
如果
- 递归调用语句的参数只与主调函数有关，即每个时刻的递归之间都是相互独立的，即没有调用全局变量
- 递归调用语句位于算法的最后
这就是一个单向递归程序。
一般参数无关的表达式结构有 \(\sum_{i=1}^{k} a_i F(n-i)\)、\(\prod_{i=1}^{k} b_i F(n-i)\) 及其组合。
特别地，我们把单向递归中递归调用语句只有一个的递归，即 \(G(\vec N) = F(n-i)\) 的递归称为尾递归。
2.2.1. 无 \(G(\vec N)\)
递归体函数无返回值，或者有返回值，但返回值没有参与运算，例如， operate() 位于 recursive() 前面。
返回递归的当前状态，对应递归表达式为 \(F(n) = f(n)\)
def func(): def recursive(flag): if flag: return operate() change_status() recursive(status()) return result() recursive(status())返回递归的初始状态，对应递归表示式为 \(F(n)=f(n_0)\)
def func(): def recursive(flag): if flag: operate() return result() change_status() return recursive(status()) recursive(status)
2.2.2. 有 \(G(\vec N)\)
显式调用返回值，对应递归表达式为 \(F(n) = G(\vec N)+f(\vec N)\)，初始状态为 \([F(n_0), F(n_1), ..., F(n_i)]\) ，没有调用全局变量
def func(i): def recursive(flag): if flag: return original_conditions() f = operate() G = multi_recursive(recursive, status()) return G + f recursive(status())例如，递归表达式 \(F(n) = 2 F(n-1) + 3 F(n-2) + 2 n + 1\) ，初始状态为 \([F(0), F(1)] = [0, 1]\)，上述结构表示为
def func(n): def F(i): if i == 0: return 0 if i == 1: return 1 G = 2 * F(i - 1) + 3 * F(i - 2) f = 2 * i + 1 return G + f return F(n)隐式传参，对应递归表达式为 \(F(n) = G(\vec N)+f(\vec N)\)，可以不传初始状态，没有调用全局变量。
这种方式其实是把递归表达式展开，是一种逻辑上的顺推操作。每次递归需要传入当前状态，包括系数的当前的状态
def func(): def recursive(flag, cond): if flag: return cond operate(cond) change_conditions() change_status() return recursive(status(), conditions()) recursive(status(), conditions())例如，递归表达式 \(F(n) = 2 F(n-1) + 3 F(n-2) + 2 n + 1\) ，终止条件为 \(F(n)>20\)，则上述结构表示为
def func(n): def F(i, r, a, b): if r > 20: return r f0 = 2 * (i - 1) + 1 f1 = 2 * (i - 2) + 1 G = a * f0 + b * f1 r += G return F(i - 1, r, a * 2, b * 3) return F(n, 2 * n + 1, 2, 3)
2.3. 非单向递归
存在多出调用语句，且与全局序列操作有关，对应表达式为 \(F(n,\vec A) = F_1(\vec{N_1},\vec A)+ F_2(\vec{N_2},\vec A)\)
def func(): global A def recursive(flag): if flag: return operate1() change_status1() recursive(status1()) operate2() change_status2() recursive(status2()) operate3() recursive(flag)上面属于两层递归，多用于二叉树的递归操作
特别地，只有
operate1()是前序遍历，只有operate2()是中序遍历，只有operate3()时后序遍历。调用语句间参数相关，意味着
operate1()、operate2()、operate3()是顺序不可变的，所以需要一个全局的变量来记录操作的顺序。例如，二叉树的中序遍历如下：
def func(n): def F(i): if i > n: return F(i * 2) A.append(i) F(i * 2 + 1) A = [] F(1) return A嵌套递归，对应一个递归表达式组 \[ F_1(n) = G_2(\vec N) + f_1(\vec N) \\ F_2(n) = G_1(\vec N) + f_2(\vec N) \]
def func(): def recursive1(flag): if flag: return operate1() change_status() recursive2(status()) def recursive2(flag): if flag: return operate2() change_status() recursive1(status()) recursive1(flag)这是一种很特殊的递归，是一种左右互搏，相互制衡的思想，可以参考“生产者-消费者”模型。这种递归比较难理解，暂时还没整理出一个通用的规律。
3. 递归转循环
虽然递归结构清晰，程序易读，但递归都要创建一个内存空间来保存现场，所以递归的效率并不高（但也有一些观点认为在某些语言中，递归比循环的效率更高），而且对于深度较高的递归，很容易出现堆栈溢出（stackoverflow）的情况，所以应用一些深度较高的递归时，优化递归的结构是一个比较重要的问题。
有理论认为，所有的递归都能转化为循环。
所以，我们可不可以把所有的递归转化为循环来优化代码？
下面先介绍递归转循环的方法。
直接法
具有初始条件的单向递归都可以直接转化为循环结构，因为单向递归结构只用到一个栈，既可倒序顺推，亦可顺序逆推。后面提到的动态规划思想也属于一种直接法。
例如，递归表达式 \(F(n) = 2 F(n-1) + 3 F(n-2) + 2 n + 1\) ，初始状态为 \([F(0), F(1)] = [0, 1]\)的循环表示为
def func(n): if n == 0: return 0 if n == 1: return 1 f0, f1 = 0, 1 for i in range(2, n + 1): f = 2 * i + 1 G = 3 * f0 + 2 * f1 + f f0, f1 = f1, G return G这种方法时间复杂度的减少是明显的，例如上面的例子时间复杂度由 \(O(2^n)\) 减少为 \(O(n)\)
显式栈法
对于任一递归 ，并不一定只具有一个栈（一般需要对全局变量进行修改的递归都不会只有一个栈），其初始条件也并不一定都能给出（例如，路径溯源问题），上述情况用直接法不可以把递归转为循环。
那只能按照逆波兰法，人工模拟操作符和数据出栈入栈，改为循环结构。这本质上是一种伪循环，代码效率并没有提升，是一种画蛇添足的方法。这种情况下，把递归转为循环都会使得代码相当冗长，也不优雅，更没必要，除了代码更加容易理解外，好像没啥特别的优点。
下面是一个递归转化为循环的例子：
def func(): global A def recursive(flag): if flag: return operate1() change_status1() recursive(status()) operate2() change_status2() recursive(status()) recursive(flag)转化为循环结构
def func(): global A stack = [] while status() or stack: while status(): operate1() stack.append(status) change_status1() status = stack.pop(-1) operate2() change_status2()例如，二叉树中序遍历的循环写法如下
def func(n): A = [] s = [] i = 1 while i <= n or s: while i <= n: s.append(i) i *= 2 i = s.pop(-1) A.append(i) i = i * 2 + 1 return A特别地，上面只有先序和中序的循环，没有后序，后序上诉写法比较麻烦，推荐使用两个栈，其循环写法如下
def func(n): A, s1, s2 = [], [], [] i = 1 s1.append(i) while s1: i = s1.pop(-1) s2.append(i) if 2 * i <= n: s1.append(2 * i) if 2 * i + 1 <= n: s1.append(2 * i + 1) while s2: i = s2.pop(-1) A.append(i) return A
所以对于同一个算法，如果是单向递归，可以转为循环，优化程序（也可以参考后面的动态规划和贪心算法对递归进行优化）；如果是非单向递归，该递归的地方还是老老实实的递归吧~
That's all~ Farewell~
