第5 章 递归和分治 一个函数调用了它自己,称为递归。递归和循环可以互相替代。一种程序设计语言,支 持递归就可以不需要支持循环,支持循环就可以不需要支持递归。例如早期的Lisp语言, 就不支持循环,只支持递归。当然,为了方便使用,程序设计语言一般都既支持递归,也支持 循环。下 面这个循环调用了n 次doSomething函数: for i in range(n): doSomething() 可以用对递归函数的调用来替代: def loop(n,f): if n == 0: return f() loop(n-1,f) loop(8,doSomething) #调用8 次doSomething 函数 从替代循环的角度看,递归和循环一样是一种手段,可以用来解决任何问题。但是递归 更多地是一种解决问题的思想———从这个角度看,也可以称递归是一种算法。 求列表a 的最大值,可以如下实现: def maxValue(a): ans = a[0] for x in a: if ans < x: ans = x return ans 也可以用递归的思想实现。思路是:如果a 的长度是1,则最大值就是a[0];否则,最 大值就是a[1:]中的最大值以及a[0]这两者中较大的那个。递归程序如下: def maxValue(a): def maxV(start): #求a[start:]中的最大值 if start == len(a)-1: #a[start:]中只有一个元素 数据结构与算法Python 语言实现 return a[start] b = maxV(start+1) #递归求a[start+1:]的最大值 if a[start] < b: return b else: return a[start] return maxV(0) 该递归函数与循环的写法相比没有什么优势,但其体现的问题分解的思路是值得掌握 的,即把规模大的问题不断分解为规模小的问题,最终加以解决。要求a 的最大值,可以先 解决一个形式相同但规模更小的子问题,即a[1:]中的最大值(因a[1:]可以看作一个比a 更短的列表)。这个子问题解决了,将其答案和a[0]做个比较,即可得到原问题的答案。 本章主要通过具体例题,分以下三种情况讲述递归的用途。 (1)替代多重循环来进行枚举。 (2)解决用递归形式定义的问题。 (3)将问题分解为规模更小的子问题进行求解。 上述三种情况其实没有也不需要有严格的区分界限。有的问题,归类为上述不止一种 情况都说得过去。例如,5.2节的例题“绘制雪花曲线”,归类为第(2)或第(3)种情况都 可以。第(3)种情况,如果分解出来的子问题不止一个且相互无重叠,一般来说就可以算是“分治”。 还有一种递归可以称为“间接递归”,例如函数A 调用了函数B,函数B 调用了函数C,函 数C 又调用了函数A,就可以说函数A、B、C 都间接递归调用了自身。本章不涉及这类递归。 5.1 用递归进行枚举 有一类问题的本质,可以归结为:有n 个变量,每个变量可以有m 种取值。这n 个变 量取值的某些组合,能够满足某个条件,欲求出所有满足条件的组合。本章习题中的“奥数 问题”“棋盘问题”,接下来要讲的案例“N 皇后问题”和“全排列”,本质都是如此。 这类问题最简单的解法就是暴力枚举所有组合,对每个组合验证其是否满足条件。这 样一共要枚举mn 种组合,可以用n 重循环来解决。当n 比较大的时候,多重循环不好写, 因此可以用递归的写法进行枚举。 5.1.1 案例:N 皇后问题(P0230) 将N 个皇后摆放在一个N 行N 列的国际象棋棋盘上,要求任何两个皇后不能互相攻击 (两个皇后在同一行,或同一列,或某个正方形的对角线上,就会互相攻击,称为冲突)。输入皇 后数N (1≤N ≤9),输出所有的摆法。无解输出“NOANSWER”。行列号都从0开始算。 输入:一个整数N ,表示要把N 个皇后摆放在一个N 行N 列的国际象棋棋盘上。 输出:所有的摆放放案。每个方案一行,依次是第0行皇后位置,第1行皇后位置,…, 第N -1行皇后位置。多种方案输出顺序如下:优先输出第0行皇后列号小的方案。如果 两个方案第0行皇后列号一致,那么优先输出第1行皇后列号小的方案,以此类推。 50 递归和分治 第5章 样例输入 4 样例输出 1 3 0 2 2 0 3 1 解题思路:在皇后数目不确定的情况下,用循环解决比较麻烦,因此可以采用递归的方 式进行枚举。程序如下: #prg0350.py 1. result = [0] * 12 #本程序最多能解决12 皇后问题 2. #result[i]表示第i 行的皇后已经放在了result[i]列 3. def isOk(n,pos): #判断第n 行的皇后放在第pos 列是否和已经摆好的皇后冲突 4. for i in range(n): #检查位置pos 是否会和前0~n-1 行已经摆好的皇后冲突 5. if result[i] == pos or abs(i-n) == abs(result[i] - pos): 6. return False 7. return True 8. def queen(N,i): #解决N 皇后问题,现在第0 行到第i-1 行的i 个皇后已经摆放好了 9. #要摆放第i 行的皇后, 10. if i == N: #已经摆好了N 个皇后,说明问题已经解决,输出结果即可 11. for k in range(N): 12. print(result[k], end=" ") 13. print("") 14. return True 15. succeed = False 16. for k in range(N): #枚举所有位置 17. if isOk(i,k): #看可否将第i 行皇后摆在第k 列 18. result[i] = k #可以摆在第k 列,就摆上 19. succeed = queen(N,i+1) or succeed #接着去摆放第i+1 行的皇后 20. return succeed 21. N = int(input()) 22. if not queen(N,0): 23. print("NO ANSWER") queen函数返回值为True或者False,queen(N ,i)的返回值表示:当前,前i 个皇后已 经摆好且不冲突,它们的摆法放在result[0:i]中,在不改变这前i 个皇后的摆法的前提下, 继续往下摆放,最终能否找到至少一种成功的N 皇后摆法。在第16行,函数试图为第i 行 的皇后找到所有和前i 个皇后不冲突的位置(所谓“枚举”,就体现在本行),每找到一个,就 摆放之,然后递归调用一次queen(N ,i+1)继续后面皇后的摆放;如果找不到,则返回 False,表示在当前情况下,最终无法摆放成功。 第14行:由于函数是递归调用的,所以有几个解,本行就会被执行几次。例如,在第0 行皇后摆在第0列的情况下,若执行queen(8,1)最终会成功,本行会得到执行;在第0行皇 后摆放在第1列的情况下,若执行queen(8,1)最终也会成功,本行又会得到执行。实际上, 如果有k 个解的第0行皇后都是摆放在第0列的,则会有k 次执行到本行时,第0行皇后是 51 数据结构与算法Python 语言实现 摆放在第0列的。 第15行:succeed表示在当前情况下,再往下摆能否至少找到一个解,先假定为False。 第18行:假设找到的第一个合法摆放位置是k1,第i 行皇后摆放在第k1 列的情况下, 会继续执行queen(N ,i+1),从此处一直递归下去,有可能会找到多种N 皇后的最终合法 摆放方案,即多次走到第11行,输出多个解。这些解的第0行到第i 行的摆放方案都是相 同的,例如,第i 行都是摆放在k1 位置。queen(N ,i+1)执行过程中经历层层多分支递归, 终究会返回,返回后回到第16行的for循环,继续寻找下一个可行的第i 行摆放位置k2,然 后再继续递归下去。 因此上面的程序会输出所有的解。 第19行:在第16行开始的循环中,只要有一次执行本行时queen(N ,i+1)返回True, succeed的值就会是True,意味着在当前情况下最终能够摆放成功。 本程序中,result列表中的一个元素,本质上就相当于多重循环解法里的一个循环控制 变量,它们都是表示一行皇后的位置的。 请注意:如果要将程序改写成找到一个解就结束,则只需要将第19行替换为下面 两行: #prg0351.py if queen(N,i+1): #接着去摆放第i+1 行的皇后 return True 这样的话,摆放第i行皇后的时候,一旦发现一个能导致最终摆放成功的摆法,就不会 去尝试第i行的下一个摆法,因此对每行的皇后,都只找到一个能导致最终成功的摆法,于 是程序的第11行只会执行1次,程序只输出一个解。 N 皇后问题的本质,是有N 个变量,这N 个变量取值的某些组合,能够满足某个条件, 要求出这些满足条件的组合。下面全排列问题,习题中的棋盘问题本质都是如此,都可以用 类似N 皇后问题的办法解决。 5.1.2 案例:全排列(P0240) 给定一个由不同的小写字母组成的字符串,输出这个字符串的所有排列。假设对于小 写字母有‘a’< ‘b’< … < ‘y’< ‘z’,而且给定的字符串中的字母已经按照从小到大的 顺序排列。 输入:输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在 1到6之间。 输出:输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在 前面。字母序如下定义。 已知S =s1s2…sk ,T =t1t2…tk ,则S < T 等价于:存在p (1 ≤p ≤k),使得 s1=t1,s2=t2,…,sp - 1=tp - 1,sp 1时,n 的阶乘是n 乘以(n-1)的阶乘。 第(2)句话,定义“阶乘”这个概念的时候,用到了“阶乘”这个词,看上去像是循环定义, 让人无法理解。但是,由于有第(1)句话的存在,上面这两句“自然数n 的阶乘”的定义,就 是严密和可以理解的。可以说第(2)句话的形式是递归的,第(1)句话就是递归的终止条件。 按照上面的定义方式,求自然数n 的阶乘的函数可以写成: def factorial(n): if n == 1: return 1 return n * factorial(n-1) 这是最简单的用递归函数解决递归形式的问题的例子。 在上面的程序中,判断“n==1”是否为真是基本操作,即进行次数最多的操作。设求 n 阶乘的基本操作次数为T(n),则有: T(n)=1+T(n-1)=1+1+T(n-2)=1+1+1+T(n-3)=…=1+1+…+T(1)= 1+1+…+1(n 个1) 所以函数的复杂度是O(n)。 5.2.1 案例:波兰表达式(P0250) 波兰表达式是一种把运算符前置的算术表达式。例如,一般形式的表达式2+3的波 兰表示法为+23。波兰表达式的优点是计算时不需要考虑运算符的优先级,因此不必用 括号改变运算次序,例如,(2+3)*4的波兰表示式为* +234。本题求解波兰表达式 的值,其中运算符包括+、-、*、/四个。 输入:输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。 输出:输出为一行,表达式的值。 样例输入 * + 11.0 12.0 + 24.0 35.0 样例输出 1357.000000 虽然什么是“波兰表达式”不难理解,但是题目其实并没有给出“波兰表达式”的准确定 义。波兰表达式可以用递归的形式准确定义如下。 (1)一个数是一个波兰表达式,其值就是该数本身。 54 递归和分治 第5章 (2)若一个波兰表达式不是一个数,则其形式为:“运算符波兰表达式1 波兰表达式 2”,其值是以“波兰表达式1”的值作为第一操作数,以“波兰表达式2”的值作为第二操作数, 进行“运算符”所代表的运算后的值。“运算符”有加减乘除4种,分别表示为“+”“-” “*”“/”。 根据上述定义,可以写出解题程序如下。 #prg0370.py 1. def polishExp(exp): 2. N = 0 3. def polish(): 4. nonlocal N 5. if exp[N] == '+': 6. N = N + 1 7. return polish() + polish() 8. elif exp[N] == '-': 9. N = N + 1 10. return polish() - polish() 11. elif exp[N] == '*': 12. N = N + 1 13. return polish() * polish() 14. elif exp[N] == '/': 15. N = N + 1 16. return polish() / polish() 17. else: 18. result = float(exp[N]) 19. N = N + 1 20. return result 21. return polish() 22. exp = input().split() 23. print('%.6f' % polishExp(exp)) 第2行:N 相当于一个指针,表示polish函数被调用时,应该从字符串列表exp中下标 为N 的元素开始,取出若干个元素(假设x 个)构成一个波兰表达式,计算出其值并返回。 而且polish函数还必须让N 变为N +x,以便下一次调用polish函数时可以从正确的位置 继续取元素。请注意,这里所说的“若干个元素”,其实元素个数是确定的,并不存在多种选 择。例如,N==0时调用polish(),一定是将exp中的所有元素都取出作为一个波兰表 达式。第 5行到第7行:按照波兰表达式定义,如果exp[N ]是“+”,则其后面一定跟着两个 波兰表达式。“+”取走后,N 的值需要加1。然后调用一次polish()取出第一个波兰表达 式并算出值,且让N 推进到合适位置,再调用一次polish()取出第二个波兰表达式,算出 值,和第一个波兰表达式的值相加后返回。当然,第二次调用polish()的时候也会推进N 到合适位置。 第17行:按照波兰表达式定义,如果exp[N ]不是运算符,则其一定是一个数。那么取 出的波兰表达式就是exp[N ],其值为float(exp[N ])。 由于只需要从头到尾扫描整个表达式一遍,所以复杂度是O(n)。 55 数据结构与算法Python 语言实现 5.2.2 案例:绘制雪花曲线 篇幅所限,请扫二维码(绘制雪花曲线)查看本小节剩余内容。 5.3 用递归进行问题分解 递归解决问题的一种特别常用的基本思路是:要解决某一问题,可以先做一步,做完一 步以后,剩下的问题也许就会变成和原问题形式相同但规模更小的子问题,那就可以递归求 解了。第一步如果有多种选择,则要枚举第一步的所有选择。当然,还需要归纳出不需要递 归就能直接解决的边界条件。 5.3.1 案例:上台阶(P0260) 有n 级台阶(0