【程序设计】6.2 [重复用] 递归 *
6.2 递归*
有了自定义函数就可以写出递归程序了，我们再来看阶乘运算，这是个好例子。
我们知道，n!=(n-1)!*n，也就是说，如果我们知道 (n-1)! 后，就可以再用乘法来计算出 n! 了；不过 n=0 时要特殊处理，因为这时候 (n-1)! 没有意义了，不能靠计算 (0-1)! 来计算 0!。
用这个思路再写一个计算阶乘的自定义函数。
A |
B |
C |
|
1 |
func factorial(n) |
if n==0 |
return 1 |
2 |
return factorial(n-1)*n |
||
3 |
=factorial(0) |
=factorial(1) |
=factorial(10) |
在自定义函数 factorial 中，它调用了自己。这种编写函数代码的方法称为递归。
我们来分析这个函数的执行过来。如果参数 n 是 0，那么在 B1 格的条件成立，继续执行 C1 格，返回 1，函数结束，没问题。顺便说一句，当自定义函数执行到 return 语句时就会结束函数的执行并返回，不管后面还有没有语句了。
如果参数 n 是 1，执行到 B1，条件不成立了，就要执行 B2 格，这时候先要用 n-1 也就是 1-1=0 作为参数再调用这个函数，再次进入这个函数后，参数 n 变成 0 了，刚才在调用时等于 1 的 n 被暂存起来了。现在 B1 的条件又成立了，于是返回 1 再退回调用前它的 B2 格，刚才暂存的 n 恢复了成 1 了，于是计算出 1*1=1 返回，也没有问题。
如果参数 n 是 2，也会执行到 B2 格，这时候会把 n-1=2-1=1 当参数传入这个函数，同时暂存等于 2 的 n。从上面的分析我们知道，它会返回 1，然后再恢复 n 的值为 2，那么参数是 2 的时候函数会返回 1*2=2，没算错。
……
只要 n-1 的阶乘能被正确计算，那么当前参数 n 的阶乘也能被正确计算。
递归有点像我们中学学过的数学归纳法。想证明和 n 相关的命题成立，只要证明这两步：
1) n=0 时成立；
2) 如果 n-1 时成立，那么 n 时也成立。
递归也是类似，如果我们想做一个和 n 相关的计算，直接计算可能比较麻烦，那么只要会做这样两步：
1) n=0 时我们会算；
2) 如果 n-1 相关的计算已经算出来了，我们就会算 n 相关的计算。
我们就用上面这种办法计算出阶乘。
我们再尝试一下前面做过的斐波那契数列的第 n 项，它的规则是这样：
1)F(1)=F(2)=1
2)F(n)=F(n-1)+F(n-2)
用递归方法写出的代码也很简单：
A |
B |
C |
|
1 |
func fibonacci(n) |
if n<=2 |
return 1 |
2 |
return fibonacci(n-1)+fibonacci(n-2) |
||
3 |
=fibonacci(1) |
=fibonacci(3) |
=fibonacci(10) |
这个代码对 n 递归时依赖了 n-1 和 n-2 时的两个结果，而且要特殊处理的初始情况也有 1 和 2 两个。
写递归代码，一定要注意必须有判断初始情况，如果忘了这个判断，递归就变成死循环而再也回不来了，而且这个死循环会很容易导致内存溢出。这是因为，每次递归再次进入函数体时，当前的变量值都会暂存起来等待退回来时恢复，如果不停地进入而没有退回，这些变量占用的空间很快就会超出计算机的存储容量。
细心的读者也能分析出来，用递归的办法来计算阶乘和斐波那契数列并不划算，这两段递归代码的运算量和占用的存储空间要远大于前面写过的循环办法，这里使用递归只作为教学例子，因为逻辑比较简单容易理解体会递归的原理。
我们再做个不用递归就比较难做的例子，计算 n 的全排列。
n 的全排列是指把 1,2,…,n 这 n 个数排成一队，将所有不同的排法都列出来。如果 n=3 时有 6 种：[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]。n=4 是有 24 种，全排序的数量是 n!。
直接想排出这 n! 种排列是不太容易的，如果用递归的办法就比较简单。
1)n=1 的时候，只有一种就是 [1]
2) 如果 n-1 时的全排列已经有了，假定是序列 p（它应该是二层的序列，每个成员是一种排列），现在我们只要针对 p 的每个成员，把 n 排到它的第 1、第 2、…、第 n-1 个位置之前以及追加到最后这 n 种位置上，得到 n 个新的排列，再把这些新排列（每个 p 的成员都对应有 n 个）都收集起来就可以了。
用这个思路写出代码：
A |
B |
C |
|
1 |
func permutation(n) |
if n==1 |
return [[1]] |
2 |
=permutation(n-1) |
=[] |
|
3 |
for B2 |
=n.(B3.to(#-1)|n|B3.to(#,)) |
|
4 |
>C2=C2|C3 |
||
5 |
return C2 |
||
6 |
=permutation(4) |
=A6.len() |
|
A1 为 1 时，直接返回结果 [[1]]，注意要返回成二层序列。A1>1 时，先准备 C2 为空用于存储结果，递归调用本函数，计算出 A1-1 的全排列然后循环它，针对其每个成员，在 C3 中生成 A1-1 个把 A1 排到第 1、第 2、…、第 A1-1 位置前及追加到最后的 A1 个新排列，再把这些新排列拼到 C2 后面。循环结束时 C2 就存好了 A1 的全排序，把它返回即可。
把问题再改一下，计算 n 的 m 排列，即在 1,2,…,n 中挑 m 个不同的数来排列，这时候有两个参数了，情况比刚才要复杂一些，和斐波那契数列类似，需要两次调用递归函数。
1)m=1 时，有 n 种，即 [[1],…,[n]]；
2) n>m 时，n-1 的 m-1 排列和 n-1 的 m 排列都有之后，分别记为 p 和 q，那么只要在 p 的成员中按上面的办法的各个位置上插入 n 就可以得到新的 m 排列（每个 p 成员会对应 m 个新排列，这些都是含有 n 的），再和 q（这些是没有 n 的）合并，就得到了 n 的 m 排列。
3) n=m，只要处理第 2 步的 p 就可以了，也就相当于刚才的全排列。
A |
B |
C |
|
1 |
func permutation(n,m) |
||
2 |
if m==1 |
return n.([~]) |
|
3 |
=permutation(n-1,m-1) |
=[] |
|
4 |
for B3 |
>C3=C3|m.(B4.to(#-1)|n|B4.to(#,)) |
|
5 |
if n>m |
>C3=C3|permutation(n-1,m) |
|
6 |
return C3 |
||
7 |
=permutation(5,3) |
=A7.len() |
|
这段代码稍一些复杂了，但困难的地方并不是代码本身的编写，而是想出这个计算方法，也就是数学上该如何解决问题。再回忆一下我们在循环那一章结束时说过的，程序语言并不能帮我们找到解决问题的办法，只会帮我们实现已经想出来的解法。
为了看清过程，我们把步骤分开写了。在我们熟练之后，这个代码还可以更紧凑一点。
A |
B |
C |
|
1 |
func permutation(n,m) |
||
2 |
if m==1 |
return n.([~]) |
|
3 |
=permutation(n-1,m-1) |
=B3.(m.(B3.~.to(#-1)|n|B3.~.to(#,))) |
|
4 |
return C3.conj()|if(n>m, permutation(n-1,m),[]) |
||
5 |
=permutation(5,3) |
=A5.len() |
|
比较复杂的是 C3，这是个两层循环函数，表达式中用到了内层的 #和外层的 ~, 结果会得到一个多层序列。B3 本身会返回一个两层序列（每个成员是一个排列），C3 将 B3 中每个成员排列扩展成 B1 个排列构成的序列，这样会得到一个三层序列（每个成员的成员是一个排列）。B4 中的 conj 函数用于多层序列，将其作为成员的序列拼接起来，相当于在所有成员之间执行 | 运算，C3.conj()就是 B1*B3.len() 个排列构成的序列了，| 右边的容易理解了。
不过这样确实难懂了一点，有时候代码写长一些也不是坏事。
