第14章递推与递归 递推是计算机数值计算中的重要算法，递推的思路是通过数学推导，将复杂的运算化 解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。 递归算法在可计算性理论中占有重要地位，也是算法设计中的比较巧妙的方法，它写 出的程序较简短，可以使某些看起来不易解决的问题变得容易解决，在程序设计中常常有 着独特的作用。 14.1递推 14.1.1递推思想 以我们已经比较熟悉的Fibonacei数列问题为例，在该问题的条件中，最前面两项是已 知的，即FT1=0,F21。第二项之后的每一项都是前面相邻两项的和，即：>2时有F[nF F[-1+F-2引。在这样的条件下，我们可以根据所给定的初始值以及相邻项之间的关系， 依次求得F3队、F[4、F.后面每一项的值。 在这类问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有 一定的关联关系，这种关联关系一般是通过一个特定的关系式来表示。求解这类问题时我 们就从初始的一个或若干数据项（比如这里的F0,F2)出发，通过类似于FF F-1+F[n-2]这样特定的关系式逐步推进，从而得到最终结果。这种求解问题的方法叫“递 推法”。 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用 于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知 条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之 间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决 递推法有两种形式，其中已知初始值，通过递推关系式求出最终结果的递推方式称为 顺推法：己知最终结果，通过递推关系式求出初始值的递推方式称为倒推法。无论顺推还 是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简 单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了 通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。 一般说来 可以将递推算法看成是一种特殊的迭代算法。（在解题时往往还把递推问题表现为迭代形 式，用循环处理。所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值， 每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方 法称为迭代。)
第 14 章 递推与递归 递推是计算机数值计算中的重要算法，递推的思路是通过数学推导，将复杂的运算化 解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。 递归算法在可计算性理论中占有重要地位，也是算法设计中的比较巧妙的方法，它写 出的程序较简短，可以使某些看起来不易解决的问题变得容易解决，在程序设计中常常有 着独特的作用。 14.1 递推 14.1.1 递推思想 以我们已经比较熟悉的 Fibonacci 数列问题为例，在该问题的条件中，最前面两项是已 知的，即 F[1]=0，F[2]=1。第二项之后的每一项都是前面相邻两项的和，即：n>2 时有 F[n]= F[n–1]+F[n–2]。在这样的条件下，我们可以根据所给定的初始值以及相邻项之间的关系， 依次求得 F[3]、F[4]、F[5].后面每一项的值。 在这类问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有 一定的关联关系，这种关联关系一般是通过一个特定的关系式来表示。求解这类问题时我 们就从初始的一个或若干数据项（比如这里的 F[1]=0，F[2]=1）出发，通过类似于 F[n]= F[n–1]+F[n–2]这样特定的关系式逐步推进，从而得到最终结果。这种求解问题的方法叫“递 推法”。 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用 于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知 条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之 间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决。 递推法有两种形式，其中已知初始值，通过递推关系式求出最终结果的递推方式称为 顺推法；已知最终结果，通过递推关系式求出初始值的递推方式称为倒推法。无论顺推还 是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简 单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了 通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来 可以将递推算法看成是一种特殊的迭代算法。（在解题时往往还把递推问题表现为迭代形 式，用循环处理。所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值， 每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方 法称为迭代。）
14.1.2求解递推关系的方法 有一类问题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如 下简捷的递推关系式： f=g(fn1)或者fn1=g(fn) 这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或最终结果） 入手，一步步地按递推关系式递推，直至求出最终结果（或初始值）。很多程序就是按这样 的方法逐步求解的。如果对一个问题，我们要是能找到后一项数与前一项数的关系并清楚 其起始条件（或最终结果），相对就比较容易解决，让计算机一步步计算就是了。让高速的 计算机从事这种重复运算，可真正起到“物尽其用”的效果。 递推分倒推法和顺推法两种形式，两者的分析思路如图14.1所示： 由题意（或递推关系）确定初始值： 由题意（或递推关系）确定最终结果[： 求出顺推关系式g(f小： 求出倒推关系式f=g(): 输出顺推结果： 输出倒推结果： a顺推 b逆推 图14.1顺推与逆推 由此可见，递推算法的时间复杂度一般为O(),不管是顺推还是逆推的问题，除了 小部分问题的初始条件（或最终结果）在问题描述中明确给定外，其余大多数问题都需要我 们通过对问题的分析与化简而确定，其递推式更需要对实际问题的仔细梳理与归纳分析而 得到，因此解决递推问题的基础是问题分析与归纳。 14.13递推关系的建立 解决递推类型问题有三个重点：一是如何建立正确的递推关系式，二是递推关系有何 性质，三是递推关系式如何求解。 其中核心问题是如何建立递推关系。建立递推关系的关键在于寻找第项与前面（或后 面)几项的关系式，以及初始项的值（或最终结果值）。它不是一种抽象的概念，而是针对某 一具体题目或一类题目而言的。 下面我们通过一些比较经典的递推问题实例，来进一步展示问题中递推关系的建立、 边界条件的获取以及在此基础上递推求解过程的实现。 2
2 14.1.2 求解递推关系的方法 有一类问题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如 下简捷的递推关系式： fn = g ( fn-1 ) 或者 fn-1 = g '( fn ) 这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件(或最终结果) 入手，一步步地按递推关系式递推，直至求出最终结果(或初始值)。很多程序就是按这样 的方法逐步求解的。如果对一个问题，我们要是能找到后一项数与前一项数的关系并清楚 其起始条件(或最终结果)，相对就比较容易解决，让计算机一步步计算就是了。让高速的 计算机从事这种重复运算，可真正起到“物尽其用”的效果。 递推分倒推法和顺推法两种形式，两者的分析思路如图 14.1 所示： 由此可见，递推算法的时间复杂度一般为 O(n)，不管是顺推还是逆推的问题，除了一 小部分问题的初始条件(或最终结果)在问题描述中明确给定外，其余大多数问题都需要我 们通过对问题的分析与化简而确定，其递推式更需要对实际问题的仔细梳理与归纳分析而 得到，因此解决递推问题的基础是问题分析与归纳。 14.1.3 递推关系的建立 解决递推类型问题有三个重点：一是如何建立正确的递推关系式，二是递推关系有何 性质，三是递推关系式如何求解。 其中核心问题是如何建立递推关系。建立递推关系的关键在于寻找第 n 项与前面(或后 面)几项的关系式，以及初始项的值(或最终结果值)。它不是一种抽象的概念，而是针对某 一具体题目或一类题目而言的。 下面我们通过一些比较经典的递推问题实例，来进一步展示问题中递推关系的建立、 边界条件的获取以及在此基础上递推求解过程的实现。 由题意(或递推关系)确定最终结果 fn； 求出倒推关系式 fi-1=g' (fi)； 从最终结果 fn出发进行倒推: for(i=n;,i>1;i-) fi-1←g' (fi)； 输出倒推结果 fl； 求出顺推关系式 fi=g(fi-1)； 从边界条件 f1 出发进行顺推: for(i=2;,i<=n;i++) fi←g(fi-1)； 输出顺推结果 fn； a. 顺推 b. 逆推 图 14.1 顺推与逆推 由题意(或递推关系)确定初始值 f1；
14.2递推设计实例 14.2.1简单Hanoi塔问题 【例14.1】Hanoi塔移动次数问题 Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大 图142 Hanoi塔移动次数 到小依次套在a柱上，如图14.2所示 要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘： (2)圆盘只能在三个柱上存放： (3)在移动时程中，不允许大盘压小盘 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？ 分析： 设hm为n个盘子从a柱移到c柱所需移动的盘次。下面从最简单情况开始讨论： (1)当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h=1。 (2)当n=2时，分为以下三个过程 首先，将a柱上面的小盘子移动到b柱上去： 然后，将大盘子从a柱移到c柱： 最后，将b柱上的小盘子移到c柱上。 共记3个盘次，故h2=3。 (3)依次类推，当a柱上有nn>2)个盘子时，也分为以下三个过程： 首先，借助c柱把上面的n-1个盘子移动到b柱上，需要移动h个盘次： 然后，把a柱最下面的盘子移动到c柱上，需要移动1个盘次： 最后，借助a柱把b柱上的n-1个盘子移动到c柱上，需要移动hm1个盘次： 总共移动h1+1+ha1个盘次。 归纳： 由以上分析可得到 ∫递推关系式： hm-2hm-1+1(>-2) 递推边界条件：h=1 3
3 14.2 递推设计实例 14.2.1 简单 Hanoi 塔问题 【例 14.1】Hanoi 塔移动次数问题 Hanoi 塔由 n 个大小不同的圆盘和三根木柱 a，b，c 组成。开始时，这 n 个圆盘由大 到小依次套在 a 柱上，如图 14.2 所示。 要求把 a 柱上 n 个圆盘按下述规则移到 c 柱上： （1）一次只能移一个圆盘； （2）圆盘只能在三个柱上存放； （3）在移动过程中，不允许大盘压小盘。 问将这 n 个盘子从 a 柱移动到 c 柱上，总计需要移动多少个盘次？ 分析： 设 hn为 n 个盘子从 a 柱移到 c 柱所需移动的盘次。下面从最简单情况开始讨论： （1） 当 n=1 时，只需把 a 柱上的盘子直接移动到 c 柱就可以了，故 h1=1。 （2） 当 n=2 时，分为以下三个过程： 首先，将 a 柱上面的小盘子移动到 b 柱上去； 然后，将大盘子从 a 柱移到 c 柱； 最后，将 b 柱上的小盘子移到 c 柱上。 共记 3 个盘次，故 h2=3。 （3） 依次类推，当 a 柱上有 n(n>2)个盘子时，也分为以下三个过程： 首先，借助 c 柱把上面的 n-1 个盘子移动到 b 柱上，需要移动 hn-1 个盘次； 然后，把 a 柱最下面的盘子移动到 c 柱上，需要移动 1 个盘次； 最后，借助 a 柱把 b 柱上的 n-1 个盘子移动到 c 柱上，需要移动 hn-1 个盘次； 总共移动 hn-1+1+hn-1 个盘次。 归纳： 由以上分析可得到： 递推关系式： hn=2hn-1+1 (n>=2) 递推边界条件： h1=1 a b c 图 14.2 Hanoi 塔移动次数
程序如下： #include <stdio.h> #include <stdlib.h> #define N 64 int main() int i.n long lo ng h[N+1]; an(d) h11=1 for(i=2;i<=n;i++) h[i]=2*h[i-1]+1: for(i=l:i<=n:itt) printf ("311d\n",h[i]) return 0; 14.2.2捕鱼问题 【例14.2】捕鱼问题 A、B、C、D、E五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地 方睡着了。A第一个醒来，它将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回 家去了。B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E依次醒来，也都按同样的办法分鱼。问：五人至少合伙捕到多少条鱼？每个人醒 来后看到的鱼数是多少条： 分析： (1)数据表示： A、B、C、D、E五人的编号分别为1、2、3、4、5。定义整型数组fish,其中数组 元素fish[k]表示第k个人所看到的鱼数，即：fsh[山表示A看到的鱼数，fish[2]表示B所 看到的鱼数，依此类推。 (2)顺推关系及其局限： 如果试图用顺推的方式来求解的话，由题意可得到fish1]、fish[2]、fsh3引、fish4、 fish5]之间的如下关系： Eish[1]:A所看到的鱼数也是合伙捕到鱼的总数 fish[2]=(fish【1]-1)*4/5:B所看到的鱼 fish[3]=(fish[2]-1)*4/5:C所看到的鱼数 4
4 程序如下： #include <stdio.h> #include <stdlib.h> #define N 64 int main() { int i,n; long long h[N+1]; scanf("%d",&n); h[1]=1; for(i=2;i<=n;i++) { h[i]=2*h[i-1]+1; } for(i=1;i<=n;i++) { printf("%lld\n",h[i]); } return 0; } 14.2.2 捕鱼问题 【例 14.2】捕鱼问题 A、B、C、D、E 五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地 方睡着了。A 第一个醒来，它将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回 家去了。B 第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E 依次醒来，也都按同样的办法分鱼。问：五人至少合伙捕到多少条鱼？每个人醒 来后看到的鱼数是多少条？ 分析： （1）数据表示： A、B、C、D、E 五人的编号分别为 1、2、3、4、5。定义整型数组 fish，其中数组 元素 fish[k]表示第 k 个人所看到的鱼数，即：fish[1]表示 A 看到的鱼数，fish[2]表示 B 所 看到的鱼数，依此类推。 （2）顺推关系及其局限： 如果试图用顺推的方式来求解的话，由题意可得到 fish[1]、fish[2]、fish[3]、fish[4]、 fish[5]之间的如下关系： fish[1]：A 所看到的鱼数也是合伙捕到鱼的总数。 fish[2]=(fish[1]–1)*4/5：B 所看到的鱼数 fish[3]=(fish[2]–1)*4/5：C 所看到的鱼数
fish[4]=(fish[3]-1)*4/5:D所看到的鱼数 fish[5]=(Eish【4]-1)*4/5:E所看到的鱼数 归纳成一般递推关系式即： fish[i]=(fish[i-1]-1)*4/5 1=2,3,5 这个公式适用于已知A看到的鱼数去推算B看到的鱼数，再推算C看到的鱼数，. 先枚举fsh)的值，如果fsh的值可以按照上面的顺推关系推出符合要求的fsh2]、 fish3引、fsh[4]、fish5],则此时的fish1]即为要求的最少鱼数。否则，如果给定的fish[1] 不能保证后续值能够完全推导出来，说明该值不符合要求，让fs[1]加1后再重新进行试 探，直到找到后续值能够完全推导出来的sh[)为止。 由于初始A看到的鱼数fsh[1]没有简洁的条件进行判断，只能从最小的正整数1开始 进行枚举，枚举的效率很低，因此用顺推的办法求解并不方便。 (3)逆推关系及求解时程 相对顺推米说，逆推求解可能更加简单方便。因为E醒来时所看到的鱼数最少，且有 较为简单的条件可以描述，所以可以试着从E看到的鱼数往前逆推，即先由E逆推D看到 的，再由D逆推C看到的， .,最后推出A所看到的。 此时sS)仍然表示E所看到的鱼数，根据题意该数应该满足被5整除后余1，即： fish[5j85=】 ish4]表示D所看到的鱼数，这个数既要满足： fish[4]-fish[5]*5/4+1 又要满足： f1sh[4185==1 按照同样的规律往回推导，与fish4一样，fish3)、fish2、fish1]也要满足如下的条 件，即： fish[i-1]=fish[i]*5/4+1(i=5,4,2) fish【i】&5==1 (i=5,4,.,1) 题目要求的fsh[1),可以根据上面的关系从fsh5)开始往前逆推。由于所求为最少的 鱼数，可以从满足条件的最小s5]值开始进行枚举，由题意可知E所看到的鱼数最少 为6条，即ish[5)的最小值为6，下面将ish[5)取值为6开始进行试探。如果当前fish) 的值可以依次求得的ish4、fish3小、fish[2小、sh,且所求均满足上述条件，则找到了 最少的鱼数。如果求得的某一个fsh们不满足条件，说明fsh5]的初值不合适，让fsh[5 增加5再试，直至可以递推到所有fsh[是整数且除以5之后的余数是1为止。 程序如下： #include <stdio,h> int main() 5
5 fish[4]=(fish[3]–1)*4/5：D 所看到的鱼数 fish[5]=(fish[4]–1)*4/5：E 所看到的鱼数 归纳成一般递推关系式即： fish[i]=(fish[i–1]–1)*4/5 i=2，3，.，5 这个公式适用于已知 A 看到的鱼数去推算 B 看到的鱼数，再推算 C 看到的鱼数，. 先枚举 fish[1]的值，如果 fish[1]的值可以按照上面的顺推关系推出符合要求的 fish[2] 、 fish[3]、fish[4]、fish[5]，则此时的 fish[1]即为要求的最少鱼数。否则，如果给定的 fish[1] 不能保证后续值能够完全推导出来，说明该值不符合要求，让 fish[1]加 1 后再重新进行试 探，直到找到后续值能够完全推导出来的 fish[1]为止。 由于初始 A 看到的鱼数 fish[1]没有简洁的条件进行判断，只能从最小的正整数 1 开始 进行枚举，枚举的效率很低，因此用顺推的办法求解并不方便。 （3）逆推关系及求解过程 相对顺推来说，逆推求解可能更加简单方便。因为 E 醒来时所看到的鱼数最少，且有 较为简单的条件可以描述，所以可以试着从 E 看到的鱼数往前逆推，即先由 E 逆推 D 看到 的，再由 D 逆推 C 看到的，.，最后推出 A 所看到的。 此时 fish[5]仍然表示 E 所看到的鱼数，根据题意该数应该满足被 5 整除后余 1，即： fish[5]%5==1 fish[4]表示 D 所看到的鱼数，这个数既要满足： fish[4]=fish[5]*5/4+1 又要满足： fish[4]%5==1 按照同样的规律往回推导，与 fish[4]一样，fish[3]、fish[2]、fish[1]也要满足如下的条 件，即： fish[i–1]=fish[i]*5/4+1 （i=5，4，.，2） fish[i]%5==1 （i=5，4，.，1） 题目要求的 fish[1]，可以根据上面的关系从 fish[5]开始往前逆推。由于所求为最少的 鱼数，可以从满足条件的最小 fish[5]值开始进行枚举，由题意可知 E 所看到的鱼数最少 为 6 条，即 fish[5]的最小值为 6，下面将 fish[5]取值为 6 开始进行试探。如果当前 fish[5] 的值可以依次求得的 fish[4]、fish[3]、fish[2]、fish[1]，且所求均满足上述条件，则找到了 最少的鱼数。如果求得的某一个 fish[i]不满足条件，说明 fish[5]的初值不合适，让 fish[5] 增加 5 再试，直至可以递推到所有 fish[i]是整数且除以 5 之后的余数是 1 为止。 程序如下： #include <stdio,h> int main()