.. Kenneth Lee 版权所有 2024
:Authors: Kenneth Lee :Version: 0.1 :Date: 2024-08-23 :Status: Draft
怎样理解递归
初学计算编程的人很容易被递归算法搞晕，不知道怎么用递归来思考问题。本文来帮助读 者来增强这种思考能力。
我们之前就介绍过，现代人一般理解的计算机，都是来自冯诺依曼计算机的概念，我们的 计算都是一套“因果链”。看看下面这个程序：
.. code-block:: python
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-block:: python
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-block:: python
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的什么位置上才是正确的……这样就可以了。
这就好像我们计算鸡兔同笼的时候，我们不管鸡和兔的数量，我们只管4x+2y=腿的总数。 这儿地方通了，剩下我们只考虑列出的方程怎么解，怎么一步步消除变量，再也不关心鸡 有几条腿，几个头，兔有几条腿，几个头。
你解方程的时候还去考虑方程两边都乘上一个常数物理上表示什么，那就自己把自己搞乱 了。
但还有些“如此类推”的东西是没法用变量表示的，比如说前面这个code-3，如果向量中还 可以包括向量，而我们的要求是向量中的每个成员都要乘num。这时你拿到i的时候你就要 区分这是不是个向量了，但如果它是向量，你就还要判断它里面的内容是不是向量了……这 又是如此类推，所以，你其实只能用递归来“如此类推”。
.. code-block:: python
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-block:: python
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; # 最后的结果
你看，这里完全没有循环，但实际上就是在做了前面的循环。我们在这一层中设计的根本 不考虑跨层的关系，我们调用递归的函数和调用其他函数一样的，就使用它的接口，而不 是它的每层局部变量的值。
上面这种思维方式，有一点是重要的，就是递归的过程基本上都是值传递，我们尽量不用 引用传递，这样两层函数之间就没有什么关系了。比如你做 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 -> nnum @ vec_mul(rest) ( 不空的是否分成两段分别处理 *)
（这里我为了容易说，没有做列表成员也是列表的情形，只是比喻一下。）
用这种思路考虑那种需要积累结果的算法怎么做呢？比如下面这儿循环算法：
.. code-block:: python
a = [] for i in range(6): a.append(i*(i+1))
a会变得越来越长，递归怎样才能让a变得越来越长呢？按值传递的理论，这就应该把这个 越来越长的内容也用值传递：
.. code-block:: python
def get_long_vec(n, l): m = len(l) # m决定算到第几步 l1 = l[:] # 拷贝一个新的列表 l1.append(m(m+1)) # 0项是01，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-block:: python
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, [])
这种“所有层的函数都看到同一个全局变量，大家都往里加东西”的情况，就可以使用全局 的变量了。这种情况下，原来那些通过递归调用的循环过程，就真的仅仅就是个循环了。
前面我们讨论code-4的时候，已经看到递归是怎么没递归一次就产生一组新的变量的了。 这导致递归算法很不实用，因为空间复杂度和循环次数相关，这儿算法需要多少空间根本 就不可控。所以，在实用的程序中很少使用一般的递归算法，更多时候，我们会限定使用 尾递归。尾递归的概念很好理解：调用递归函数的时候直接返回，就是尾递归。因为进入 这个调用前，调用函数就可以释放自己的堆栈，这样就不会产生内存的积累了。
比如这个递归：
.. code-block:: python
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-block:: python
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-block:: python
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了。
最后我们写个程序来综合一下前面的知识吧，比如我们现在要做一个列出某个列表的排列 组合的函数，比如我们输入[1,2,3]，我们希望得到：::
[[1,2,3], [1,3,2], [2,1,3), [2,3,1], [3,1,2], [3,2,1]]
。这个是个典型用循环不好处理的场景，因为它不是线性变化的。但我们构造前面这张表 的时候，明显已经看到规律了：
任取一个值出来做第一个值，然后对剩下的列表做一个排列组合，就能得到这个列表。
这就是而递归过程，所以我们可以这样做：
.. code-block:: python
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，这里 要构造尾递归需要一个二维的数据结构才能记住那么多的数据。这个已经有点超出我们要 讨论的范围了，写这儿已经相当于写通用的用循环替代递归的算法了。我们找其他机会再 讨论这种问题吧。