2.51. 怎样理解递归
初学计算编程的人很容易被递归算法搞晕，不知道怎么用递归来思考问题。本文来帮助读者来增强这种思考能力。
我们之前就介绍过，现代人一般理解的计算机，都是来自冯诺依曼计算机的概念，我们的计算都是一套“因果链”。看看下面这个程序：
# code-1
1: a = 3;
2: a = a + 4;
3: a = a*2;
盯着a这个变量，第一步它等于3，这是它第二步等于7的因，a在第二步等于7是a在第一步等于3的果。这个果是第三步a等于14的因，而第三步a等于14是第二步a=7的果。
冯诺依曼计算机就是一个这样的因果链。只是常常它的因果链步止一个a，还有更多的其他状态而已。
这种基于因果链思考问题的方法，是人脑最直接的推理模式，也是我们觉得“很好想”的模型。但它效率不高，所以人还有一种思维，叫“如此类推”。怎么“如此类推”呢，比如这样：
# code-2
1: a = 3;
for i in range(1,10):
2: a = a + 4;
3: a = a*2;
它是前面思维的顺延。我们还是顺着1-2-3-2-3-2-3-...这条因果链来思考这个执行过程的，只是我们实验了其中几个重复的循环了，我们的脑子认为：后面也差不多，然后我们就开始跳过中间的过程，然后我们就指望计算机无条件一直这样执行下去，帮助我们“如此类推”了而已。
这种方法有点像方程，通过变量来思考行为，前面这个例子中的i就是过程的变量，只是过程的每一步，都和i没有什么直接关联而已。我们换一个例子：
# code-3
def vec_mul(vec, num):
new_vec = []
for i in vec:
new_vec.append(i*num);
return new_vec
vec_mul输进来一个向量，我们也不知道里面有多少个数字，所以每个数字就变成了一个变量，我们的循环拿到每个变量i，然后把它乘上num作为结果。这里的i是第几次循环，我们是不关心的，我们只用方程的思维：对于某次循环中的i，它要乘上num，然后放到new_vec的什么位置上才是正确的……这样就可以了。
这就好像我们计算鸡兔同笼的时候，我们不管鸡和兔的数量，我们只管4*x+2*y=腿的总数。这儿地方通了，剩下我们只考虑列出的方程怎么解，怎么一步步消除变量，再也不关心鸡有几条腿，几个头，兔有几条腿，几个头。
你解方程的时候还去考虑方程两边都乘上一个常数物理上表示什么，那就自己把自己搞乱了。
但还有些“如此类推”的东西是没法用变量表示的，比如说前面这个code-3，如果向量中还可以包括向量，而我们的要求是向量中的每个成员都要乘num。这时你拿到i的时候你就要区分这是不是个向量了，但如果它是向量，你就还要判断它里面的内容是不是向量了……这又是如此类推，所以，你其实只能用递归来“如此类推”。
# code-4
def vec_mul(vec, num):
new_vec = []
for i in vec:
if instanceof(i, list):
new_vec.append(vec_mul(i, num))
else:
new_vec.append(i*num);
return new_vec
这个逻辑是不是看起来很自然？其实纯粹从数学上想这个问题，这其实是很自然的。但如果我们还用前面的因果链来思考这个问题，我们就会觉得很不自然。为什么呢？
我们拿一个例子来想一下就知道了。假定我们的输入是vec_mul([[[1, 2], 3], 4], 5)。我们顺着因果链，第一次循环我们看到的结果是：:
i=[[1, 2], 3], new_vec=[vec_mul([[1, 2], 3], 5)]
好了，顺着因果链，我们就应该看被递归的vec_mul里面怎么执行了：:
上一层i=[[1, 2], 3], new_vec=[vec_mul([[1, 2], 3], 5)] （第一层）
本层：i=[1, 2], new_vec=[vec_mul([1, 2], 5)]
下层：i=1, new_vec=[5]
下层：i=2, new_vec=[5, 10]
本层：i=3, new_vec=[[5, 10], 15]
上一层i=4, new_vec=[[[5, 10], 16], 20]
这里整个问题的关键就在于，一般的循环我们眼睛里看到的是少数的几个变量，但递归制造的循环是每循环一次产生的变量就会增加一批，而它们的名字是一样的。上面这个图，到了第三行，三个i是同时存在的。三个new_vec也是同时存在的，而不是同一个状态。
所以你的脑子会晕，因为你脑子习惯是用变量来思考“当前状态”的，但这个“当前状态”是随着循环次数的增加会越来越大，你脑子处理不了。
那怎么办呢？这你需要类似方程的思路，在每层上，你只考虑那一层的变量，完全不要想上一层的问题就好了。
在code-4中，你思考new_vec.append(vec_mul(i, num))，不要想vec_mul里面怎么样，因为这里没有全部变量，大家都是自己的局部变量。你这里就是本地有一个new_vec，里面有一个循环便利输入的vec中的每个i，如果i是个列表，我希望得到vec_mul(i, num)的一个返回值。这个返回值是个和i一样形式的list，其中每个成员都乘以num，这个逻辑没有错，那这个定义就没有错。我们不考虑中间产生了多少层函数内的堆栈变量。
也就是说，我们从来不去思考前面那个展开的图。
所有的循环，本质上都是特殊的（没有额外局部变量的递归），所以，让我们用前面这样思考转化掉code-4的循环。这样我们可以深入理解一下前面这种思考方法：
# code-5
def vec_mul(vec, num): # 输入是不变的
# 现在我们需要考虑如何“降级”（reduce）整个计算，而计算的级被vec的长度
# 决定着，所以，最容易考虑的降级方法是先算其中一个，然后算剩下的。
if len(vec) == 0: # 没有内容，无法降级
return vec
elif len(vec) == 1: # 只有一个，不需要降级了
if instanceof(vec[0], list):
return [vec_mul(vec[0], num)]
else:
return [vec[0]*num]
else: # 至少有两个，降一级
n = vec[0] # 第一个数字
rest = vec[1:] # 剩下的数字
if instanceof(n, list): # 计算第一个数字
new_vec = [vec_mul(n, num)]
else:
new_vec = [n*num]
new_vec.extend(vec_mul(rest, num)) # 递归剩下的部分
return new_vec; # 最后的结果
你看，这里完全没有循环，但实际上就是在做了前面的循环。我们在这一层中设计的根本不考虑跨层的关系，我们调用递归的函数和调用其他函数一样的，就使用它的接口，而不是它的每层局部变量的值。
2.51.1. 局部变量和全局变量
上面这种思维方式，有一点是重要的，就是递归的过程基本上都是值传递，我们尽量不用引用传递，这样两层函数之间就没有什么关系了。比如你做new_vec.extend(vec_mul(rest, num))，new_vec是一个集合，rest是另一个集合，vec_mul计算的结果又是一个集合，它们互相之间没有什么关系。所以我们不需要跨调用来想问题，无论内层函数搞什么幺蛾子，反正出来的时候给的一定是它返回的值。
所以你尽量别在递归里面分配堆内存(比如new，malloc等），也不要直接访问全局变量。这样上面这个考虑问题的方法就总是成立的。就好比这个code-5的程序，我们计算new_vec的时候确实是可以在数组原地计算的，但我们每次都分配了一个新的数组，老的数组反正在堆栈中，离开以后就没有了。这样我们只要盯着输入输出那个位置，就总不会错了。
这是大部分函数式编程的基本思路，比如用Ocaml写前面这个程序，它就是这样的：:
(* code-6 *)
let rec vec_mul vec, num = match vec with
[] -> [] (* 空的时候返回一个空列表 *)
| n::rest -> n*num @ vec_mul(rest) (* 不空的是否分成两段分别处理 *)
（这里我为了容易说，没有做列表成员也是列表的情形，只是比喻一下。）
用这种思路考虑那种需要积累结果的算法怎么做呢？比如下面这儿循环算法：
# code-7
a = []
for i in range(6):
a.append(i*(i+1))
a会变得越来越长，递归怎样才能让a变得越来越长呢？按值传递的理论，这就应该把这个越来越长的内容也用值传递：
# code-8
# 我们要得到[0*1, 1*2, 2*3, ..., (n-1)*n]，所以第一步应该计算0*1，并记住还有n-1
# 步没有算完，所以递归函数在两层之间要同时传递列表和n的值。
def get_long_vec(n, l):
m = len(l) # m决定算到第几步
l1 = l[:] # 拷贝一个新的列表
l1.append(m*(m+1)) # 0项是0*1，1项是1*2……
if n == 1: # 降到1的时候就算了6次
return l1 # 递归到底了
else:
return get_long_vec(n-1, l1) # 没到底，向下递归
l = get_long_vec(6, [])
print(l)
像Ocaml这种只能写值传递的方案，你就必须这样写：:
(* code-9 *)
let rec get_long_vec n l = let m = List.length l in
match n with
1 -> None, l@(m*(m+1))
| n -> get_long_vec(n-1, l@(m*(m+1)))
等你熟悉了前面这个思维模型，这些互相影响的关系你能想得很清楚了，我们就可以把全局变量当作一种“打印”了。比如上面这个过程，如果我们认为l1.append()是一种print()，那么上面的函数就是对遍历过程的一种“顺序打印”：
# code-10
def get_long_vec(n, l):
m = len(l)
l.append(m*(m+1))
if n > 1:
return get_long_vec(n-1, l)
else:
return l
get_long_vec(6, [])
这种“所有层的函数都看到同一个全局变量，大家都往里加东西”的情况，就可以使用全局的变量了。这种情况下，原来那些通过递归调用的循环过程，就真的仅仅就是个循环了。
2.51.2. 尾递归
前面我们讨论code-4的时候，已经看到递归是怎么没递归一次就产生一组新的变量的了。这导致递归算法很不实用，因为空间复杂度和循环次数相关，这儿算法需要多少空间根本就不可控。所以，在实用的程序中很少使用一般的递归算法，更多时候，我们会限定使用尾递归。尾递归的概念很好理解：调用递归函数的时候直接返回，就是尾递归。因为进入这个调用前，调用函数就可以释放自己的堆栈，这样就不会产生内存的积累了。
比如这个递归：
# code-11
def sumadd(n, m):
x = m+n
if n==0: return x
else: return sumadd(n-1, x)
sumadd(10, 0)
最后一行我们调用sumadd()递归的时候，我们肯定当前的sumadd中的x不会有人使用了，所以这时我们降低我们的堆栈是肯定不会有问题的。这就好像调用外面一层sumadd的人，直接在调用里面已成sumadd一样，这样无论递归多少次，都不会增高堆栈。
但如果你这样写：
# code-12
def sumadd(n):
if n==0: return 0
else: return n+sumadd(n-1)
这就不是尾递归了，因为你调完递归的sumadd(n-1, x)，还要回来本函数加上n才能返回，这就不是尾递归了。同理，前面的code-4和code-5那些，都不是尾递归，因为它们在调用完递归函数，还要做一个简单的计算才能退出本函数。
一个好消息是：任何递归都可以变成尾递归。比如前面这个code-12，你要让sumadd的结果是n加上函数的值，我们就可以把这个计算也放到函数里面去做。这样就变成code-11了：我们把那个需要回到上一级函数计算的值，放到子函数的输入中，
然后我们还可以在封装一下，变成这样：
# code-13
def sumadd_tailrec(n, m):
x = m+n
if n==0: return x
else: return sumadd(n-1, x)
def sumadd(n):
subadd_tailrec(n, 0)
这里sumadd(n)不是递归函数，为了能尾递归，我们需要引入一个m来在函数之间做传递。但这儿m又不是用户需要的，所以我们先写一个尾递归的版本。然后我们再用一个没有这个m的非递归函数来调用它，外面使用的人就看不见这个m了。
2.51.3. 总结
最后我们写个程序来综合一下前面的知识吧，比如我们现在要做一个列出某个列表的排列组合的函数，比如我们输入[1,2,3]，我们希望得到：:
[[1,2,3], [1,3,2],
[2,1,3), [2,3,1],
[3,1,2], [3,2,1]]
。这个是个典型用循环不好处理的场景，因为它不是线性变化的。但我们构造前面这张表的时候，明显已经看到规律了：
任取一个值出来做第一个值，然后对剩下的列表做一个排列组合，就能得到这个列表。
这就是而递归过程，所以我们可以这样做：
# code-14
def P(v):
if len(v) == 0: return [] # 空的时候什么都返回不了
elif len(v) == 1: return [v] # 只有一个的时候就是自己了
else:
l = [] # 有两个以上，可以递归
for i in v: # 每个成员都取出来一次
v1=v[:] # 复制一份去掉了i的剩余列表
v1.remove(i)
p = P(v1) # 对剩下的列表做排列组合
for j in p: # 每个排列组合的结果都拼到i中
v2=[i] # 这里又需要一份新的
v2.extend(j) # 扩展新的
l.append(v2) # 加到列表中
return l
我们也看到了，但这不是尾递归。这儿尾递归不好做，因为它的计算也是在扩展l，这里要构造尾递归需要一个二维的数据结构才能记住那么多的数据。这个已经有点超出我们要讨论的范围了，写这儿已经相当于写通用的用循环替代递归的算法了。我们找其他机会再讨论这种问题吧。