《数据结构》课程授课教案（讲稿）第五章 递归算法

课程名称：数据结构第9周，第9讲次摘要第五章递归算法授课题目（章、节）【目的要求】通过本讲课程的学习，理解递归算法的执行过程，掌握递归算法的设计方法，理解汉诺塔问题的递归实现方法。[重点】理解递归算法的执行过程，掌握递归算法的设计方法。【难点】理解递归算法执行过程。内容【本讲课程的引入】递归概念我们并不陌生，在学习程序设计语言中我们应该接触过，这次课要进一步讲解递归算法的执行过程以及递归算法的设计方法，为我们学习后续的课程作好准备。我们要明确递归并不是一种数据结构，而是一种有效的程序设计方法。【本讲课程的内容】第5章递归算法5.1递归的概念若一个算法直接的或间接的调用自已本身，则称这个算法是递归算法。1问题定义是递推的阶乘函数的常见定义是：当x=0时[16-121=当n>0时[ nx(n-Dx..x1也可定义为：[1当n=0时6-2/=当n>0时(nx(n- 1)写成函数形式，则为：当n=0时[16-3f(n) =当>时n*f(n-1)这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称公式（6－3）是阶乘函数的递推定义式。2.问题的解法存在自调用例如：折半查找算法查找17

课程名称：数据结构 第 9 周，第 9 讲次 摘 要 授课题目（章、节） 第五章 递归算法 【目的要求】通过本讲课程的学习，理解递归算法的执行过程，掌握递归算法的设计方法，理解汉诺塔问题 的递归实现方法。 【重 点】理解递归算法的执行过程，掌握递归算法的设计方法。 【难 点】理解递归算法执行过程。 内 容 【本讲课程的引入】递归概念我们并不陌生，在学习程序设计语言中我们应该接触过，这 次课要进一步讲解递归算法的执行过程以及递归算法的设计方法，为我们学习后续的课程 作好准备。我们要明确递归并不是一种数据结构，而是一种有效的程序设计方法。 【本讲课程的内容】 第 5 章 递归算法 5.1 递归的概念 若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法。 1 问题定义是递推的 阶乘函数的常见定义是： 也可定义为： 写成函数形式，则为： 这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称公式（6– 3）是阶乘 函数的递推定义式。 2. 问题的解法存在自调用 例如：折半查找算法 查找 17

01234567第一次：下标134517183133元素值+++midlowhighx>a[mid]07234615第二次：下标17133134531元素值++lowmidhighxa[mid].！334567第三次：下标元素值13>517183133Tux--a[mid]highmid5.2递归算法的执行过程例1：阶乘的递归算法public staticlongfact(intn)throws Exception(int x;long y;if(n <o) tthrownewException("参数错！");1if(n == 0) return l:elsex=n-1;y = fact(x);return n * y:1设计一个计算3！的主函数如下，用来说明递归算法的执行过程public static void main(String args)(long fn;try(fn = fact(3):System.out.println("fn="+fn):catch(Exception e) (System.out.println(e.getMessage();11主函数用实参n=3调用了递归算法Fact（3)，而Fact(3)要通过调用Fact(2）、Fact（2）要通过调用Fact(1)、Fact(1)要通过调用Fact(O)来得出计算结果。Fact(3)的递归调用过程如下图所示，其中，实线箭头表示函数调用，虚线箭头表示函数返回，此函数在返回时函数名将带回返回值

第一次: 下标 0 1 2 3 4 5 6 7 元素值 1 3 4 5 17 18 31 33 第二次: 下标 0 1 2 3 4 5 6 7 元素值 1 3 4 5 17 18 31 33 第三次: 下标 0 1 2 3 4 5 6 7 元素值 1 3 4 5 17 18 31 33 low mid high low mid high low high mid x>a[mid] x<a[mid] x==a[mid] 5.2 递归算法的执行过程 例 1：阶乘的递归算法 public static long fact(int n) throws Exception{ int x; long y; if(n < 0){ throw new Exception("参数错！"); } if(n == 0) return 1; else{ x = n - 1; y = fact(x); return n * y; } } 设计一个计算 3！的主函数如下,用来说明递归算法的执行过程： public static void main(String[] args){ long fn; try{ fn = fact(3); System.out.println("fn = " + fn); } catch(Exception e){ System.out.println(e.getMessage()); } } 主函数用实参 n = 3 调用了递归算法 Fact(3)，而 Fact(3)要通过调用 Fact(2)、Fact(2) 要通过调用 Fact(1)、Fact(1)要通过调用 Fact(0)来得出计算结果。Fact(3)的递归调用过 程如下图所示，其中，实线箭头表示函数调用，虚线箭头表示函数返回，此函数在返回时 函数名将带回返回值

fact(2)fact(1)mainfact(3)fact(0)集44return1fn-fact(3)y-fact(1)act(2)Hact(O).↓+216return(3*y)return(2*y)return(1*y)5.3递归算法的设计方法递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到定程度的子问题可以直接求解；这样，原问题就可递推得到解。适宜于用递归算法求解的问题的充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质（2）某一有限步的子问题（也称作本原问题）有直接的解存在。当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是：（1）把对原问题的求解表示成对子问题求解的形式。（2）设计递归出口。例3设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3根标号为A，BC的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子：（2）移动过程中大盘子不能放在小盘子上面：（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。ABC034问题分析：可以用递归方法求解Ⅱ个盘子的汉诺塔问题。基本思想：1个盘子的汉诺塔问题可直接移动。个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。4个盘子汉诺塔问题的递归求解示意图如下图所示

5.3 递归算法的设计方法 递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。 递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个 相对简单且类同的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到 一定程度的子问题可以直接求解；这样，原问题就可递推得到解。 适宜于用递归算法求解的问题的充分必要条件是： （1）问题具有某种可借用的类同自身的子问题描述的性质 （2）某一有限步的子问题（也称作本原问题）有直接的解存在。 当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是： （1）把对原问题的求解表示成对子问题求解的形式。 （2）设计递归出口。 例 3 设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有 3 根标号为 A，B， C 的柱子，在 A 柱上放着 n 个盘子，每一个都比下面的略小一点，要求把 A 柱上的盘子全 部移到 C 柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能 放在小盘子上面；（3）在移动过程中盘子可以放在 A，B，C 的任意一个柱子上。 问题分析：可以用递归方法求解 n 个盘子的汉诺塔问题。 基本思想：1 个盘子的汉诺塔问题可直接移动。n 个盘子的汉诺塔问题可递归表示为，首先 把上边的 n-1 个盘子从 A 柱移到 B 柱，然后把最下边的一个盘子从 A 柱移到 C 柱，最后把 移到 B 柱的 n-1 个盘子再移到 C 柱。 4 个盘子汉诺塔问题的递归求解示意图如下图所示

算法设计：首先，盘子的个数n是必须的一个输入参数，对n个盘子，我们可从上至下依次编号为1,2，，n；其次，输入参数还需有3个柱子的代号，我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg：最后由于此算法是模拟汉诺塔问题的求解过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：MoveDiskifromPegXtoPegYpublic static voidtowers(intn,char fromPeg,char toPeg,charauxPeg)f//把n个圆盘从fromPeg借助auxPeg移至toPegif(n == 1) (System.out.println("move disk 1 from peg"+fromPeg+"to peg"toPeg);return;子towers(n.-l,fromPeg,auxPeg,toPeg);System.out.println("move disk"+n+"frompeg"+fromPeg+"to peg" + toPeg) :towers(n-l, auxPeg, toPeg, fromPeg);递归算法把移动n个盘子的汉诺塔问题分解为移动n-1个盘子的汉诺塔问题，把移动n-1个盘子的汉诺塔问题分解为移动n-2个盘子的汉诺塔问题，，把移动2个盘子的汉诺塔问题分解为移动1个盘子的汉诺塔问题。对于1个盘子的汉诺塔问题直接求解。在1个盘子的汉诺塔问题解决后，可以解决2个盘子的汉诺塔问题，，在n-1个盘子的汉诺塔问题解决后，可以解决n个盘子的汉诺塔问题。这样n个盘子的汉诺塔问题最终就得以解决。递归算法的执行过程可总结如下：递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回：返回到最外层的调用语句时递归算法执行过程结束。5.4递归过程和运行时栈递归函数的执行过程具有三个特点：（1）函数名相同；（2）不断地自调用：（3）最后被调用的函数要最先被返回。系统用于保存递归函数调用信息的堆栈称作运行时栈。每一层递归调用所需保存的信息构成运行时栈的一个工作记录栈顶的工作记录保存的是当前调用函数的信息，所以栈顶

算法设计：首先，盘子的个数 n 是必须的一个输入参数，对 n 个盘子,我们可从上至下依 次编号为 1,2,.,n；其次，输入参数还需有 3 个柱子的代号,我们令 3 个柱子的参数名分 别为 fromPeg，auxPeg 和 toPeg；最后由于此算法是模拟汉诺塔问题的求解过程，因此算 法的输出是 n 个盘子从柱子 fromPeg 借助柱子 auxPeg 移动到柱子 toPeg 的移动步骤，我们 设计每一步的移动为屏幕显示如下形式的信息： Move Disk i from Peg X to Peg Y public static void towers(int n, char fromPeg, char toPeg, char auxPeg){ //把 n 个圆盘从 fromPeg 借助 auxPeg 移至 toPeg if(n == 1){ System.out.println("move disk 1 from peg " + fromPeg + " to peg " + toPeg); return; } towers(n -1, fromPeg, auxPeg, toPeg); System.out.println("move disk " + n + " from peg " + fromPeg + " to peg " + toPeg); towers(n - 1, auxPeg, toPeg, fromPeg); } 递归算法把移动 n 个盘子的汉诺塔问题分解为移动 n-1 个盘子的汉诺塔问题，把移动 n-1 个盘子的汉诺塔问题分解为移动 n-2 个盘子的汉诺塔问题，.，把移动 2 个盘子的汉 诺塔问题分解为移动 1 个盘子的汉诺塔问题。对于 1 个盘子的汉诺塔问题直接求解。在 1 个盘子的汉诺塔问题解决后，可以解决 2 个盘子的汉诺塔问题，.,在 n-1 个盘子的汉诺塔 问题解决后，可以解决 n 个盘子的汉诺塔问题。这样 n 个盘子的汉诺塔问题最终就得以解 决。递归算法的执行过程可总结如下：递归算法的执行过程是不断地自调用，直到到达递 归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的 次序返回；返回到最外层的调用语句时递归算法执行过程结束。 5.4 递归过程和运行时栈 递归函数的执行过程具有三个特点： （1）函数名相同； （2）不断地自调用； （3）最后被调用的函数要最先被返回。 系统用于保存递归函数调用信息的堆栈称作运行时栈。 每一层递归调用所需保存的信息 构成运行时栈的一个工作记录 栈顶的工作记录保存的是当前调用函数的信息，所以栈顶

的工作记录也称为活动记录。阶乘的递归算法publicstaticlongfact(intn)throwsExceptionint x;long y;if(n<o)tthrownewException（"参数错！"）；1if(n == 0) return 1;elsex= n - 1;y = fact(x):return n * y:publicstatic voidmain(Stringargs)(long fn;try(fn = fact(3);System.out.println("fn ="+fn);catch(Exception e) (System.out.println(e.getMessage():子阶乘递归函数运行时栈的变化过程：o(a)(E)5.5递归算法到非递归算法的转换一般来说，如下两种情况的递归算法可转化为非递归算法（1）存在不借助堆栈的循环结构的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等（2）存在借助堆栈的循环结构的非递归算法。所有递归算法都可以借助堆栈转换成循环结构的非递归算法

的工作记录也称为活动记录。 阶乘的递归算法 public static long fact(int n) throws Exception{ int x; long y; if(n < 0){ throw new Exception("参数错！"); } if(n == 0) return 1; else{ x = n - 1; y = fact(x); return n * y; } } public static void main(String[] args){ long fn; try{ fn = fact(3); System.out.println("fn = " + fn); } catch(Exception e){ System.out.println(e.getMessage()); } } 阶乘递归函数运行时栈的变化过程： 5.5 递归算法到非递归算法的转换 一般来说，如下两种情况的递归算法可转化为非递归算法： （1）存在不借助堆栈的循环结构的非递归算法，如阶乘计算问题、斐波那契数列的计算问 题、折半查找问题等 （2）存在借助堆栈的循环结构的非递归算法。所有递归算法都可以借助堆栈转换成循环结 构的非递归算法

5.6设计举例例1：设计一个输出如下形式数值的递归函数。.nnnn......333221递归函数设计如下：public static voiddisplay(int n)(for(int i=l; i 0) display(n = 1);//n=l:j--)(for (int i=l ;i<=j;i++)(System.out.print(""+j);1System.out.printlnO;11例2设计求解委员会问题的算法。委员会问题是：从一个有n个人的团体中抽出k（k≤n)个人组成一个委员会，计算共有多少种构成方法。问题分析：从n个人中抽出k(k≤n)个人的问题是一个组合问题。把n个人固定位置后，从n个人中抽出k个人的问题可分解为两部分之和：第一部分是第一个人包括在k个人中，第二部分是第一个人不包括在k个人中。对于第一部分，则问题简化为从n-1个人中抽出k-1个人的问题；对于第二部分，则问题简化为从n-1个人中抽出k个人的问题。下图给出了n=5，k=2时问题的分解示意图

5.6 设计举例 例 1： 设计一个输出如下形式数值的递归函数。 n n n . n . 3 3 3 2 2 1 递归函数设计如下 ： public static void display(int n){ for(int i = 1; i 0) display(n - 1); //递归 //n=1;j-){ for (int i=1 ;i<=j;i++){ System.out.print(" "+j); } System.out.println(); } } 例 2 设计求解委员会问题的算法。委员会问题是：从一个有 n 个人的团体中抽出 k (k≤ n)个人组成一个委员会，计算共有多少种构成方法。 问题分析：从 n 个人中抽出 k(k≤n)个人的问题是一个组合问题。把 n 个人固定位置后， 从 n 个人中抽出 k 个人的问题可分解为两部分之和：第一部分是第一个人包括在 k 个人中， 第二部分是第一个人不包括在 k 个人中。对于第一部分，则问题简化为从 n-1 个人中抽出 k-1 个人的问题；对于第二部分，则问题简化为从 n-1 个人中抽出 k 个人的问题。 下图给出了 n=5, k=2 时问题的分解示意图

ABCCDCIaE0EIEICEDLCDEL当n=k或k=0时，该问题可直接求解，数值均为1，这是算法的递归出口。因此，委员会问题的递推定义式为：n当k=0时当=时comm(n, t) =31其它/comm(n-1,x-1)+comm(n-1,k)public static int Comm(int n, intk)if(nn)return0:if(k == 0) return 1;if(n ==k) return l:return Comm(n-l, k-1) + Comm(n-1, k);7例3求两个正整数n和m最大公约数的递推定义式为：当m>(gcd(m,n%m)要求：（1）编写求解该问题的递归算法：（2）分析当调用语句为Gcd(30，4)时算法的执行过程和执行结果：（3）分析当调用语句为Gcd（5，97)时算法的执行过程和执行结果：（4）编写求解该问题的循环结构算法。解答：(1)递归函数设计如下：public static int gcd(int n, intm)(if(n n) return gcd(m,n):else return gcd(m,n % m) ;

当 n=k 或 k=0 时，该问题可直接求解，数值均为 1，这是算法的递归出口。因此，委 员会问题的递推定义式为： public static int Comm(int n, int k) { if(n n) return 0; if(k == 0) return 1; if(n == k) return 1; return Comm(n-1, k-1) + Comm(n-1, k); } 例 3 求两个正整数 n 和 m 最大公约数的递推定义式为： 要求： （1）编写求解该问题的递归算法； （2）分析当调用语句为 Gcd(30, 4)时算法的执行过程和执行结果； （3）分析当调用语句为 Gcd(5, 97)时算法的执行过程和执行结果； （4）编写求解该问题的循环结构算法。 解答： (1)递归函数设计如下： public static int gcd(int n, int m){ if(n n) return gcd(m,n); else return gcd(m,n % m); }

(2)调用语句为Gcd(30，4)时，因mn，递归调用Gcd(97，5)：因mn)(tn = m;tm = n;1elsetn = n;tm=m;1while(tm != 0)(temp = tn;tn = tm;tm= temp % tm;return tn;【本讲课程的小结】递归算法是一种有效的程序设计方法，在后续的课程中我们经常会用到这种方法，所以我们要理解递归算法的执行过程以及设计方法。【本讲课程的作业】设计输出如下形式数值的函数。1223333.00n.nnn要求（1）设计成递归结构的函数（2）设计成循环结构的函数

(2)调用语句为 Gcd(30, 4)时，因 mn，递归调用 Gcd(97, 5)；因 m n){ tn = m; tm = n; } else{ tn = n; tm = m; } while(tm != 0){ temp = tn; tn = tm; tm = temp % tm; } return tn; } 【本讲课程的小结】递归算法是一种有效的程序设计方法，在后续的课程中我们经常会用 到这种方法，所以我们要理解递归算法的执行过程以及设计方法。 【本讲课程的作业】 设计输出如下形式数值的函数。 1 2 2 3 3 3 。 n n n . n 要求（1）设计成递归结构的函数 （2）设计成循环结构的函数