PPT《第11章》

第11章 递归 张坤龙zhangkl@tju.

edu.cn天津大学计算机学院 概要 递归思想递归编程使用递归解决问题图形程序中的递归用法 递归思想 递归定义是以一种事物自身定义自身的过程当定义一个英文单词时,递归定义通常没有帮助但是有些场合,递归定义却是一个一种表达概念的恰当方法在应用递归来编程前,培养递归思想是最好的方法 递归定义 考虑下面的数字列表:24, 88, 40, 37这样的列表也能这样定义: 列表是: 一个数字 或者: 一个数字 , 列表即, 列表定义尾一个数字或者一个数字后面跟一个逗号(,)再跟一个列表列表的概念被用于定义列表自身 递归定义 列表定义的递归部分,使用了多次,最终以非递归部分结束: 数字 逗号 列表

24 , 88, 40,

37 数字 逗号 列表

88 , 40,

37 数字 逗号 列表

40 ,

37 数字

37 无穷递归 所有的递归定义都应该有非递归部分和递归部分构成如果没有非递归部分,递归将无法终止这样的定义就是无穷递归非递归部分通常称作基本事件 递归定义 对于任何正整数N,N!(N的阶乘)的值定义为所有1~N(包括N)之间的所有整数的乘积此定义的递归表达如下: 1! =

1 N! = N * (N-1)!使用阶乘来定义另一个阶乘最终,基本事件是1!,1!定义为1 递归定义 5!

5 * 4!4 * 3!3 * 2!2 * 1!1

2 6

24 120 概要 递归思想递归编程使用递归解决问题图形程序中的递归用法 递归程序设计 Java中一个方法调用自身称作递归方法递归方法的代码必须能够处理基本事件和递归事件每次方法调用,必须建立新的执行环境:带有新参数和局部变量当方法结束时,控制流返回调用调用该方法的上一层方法中 递归程序设计 考虑计算1~N的求和计算这个问题的递归定义如下: 递归程序设计 // This method returns the sum of

1 to numpublic int sum (int num){ int result;

if (num == 1)result = 1;

else result = num + sum (n-1);

return result;

} 递归程序设计 main sum sum sum sum(3) sum(1) sum(2) result =

1 result =

3 result =

6 递归程序设计 需要注意的是,如果可以采用递归解决一个问题,并不意味着我们就应该采用递归取解决它例如,我们不应该采用递归取解决1~N的求和计算问题,因为循环迭代求和的方法更易于理解然而,对于其他一些问题,递归提供了一种简洁的解决方法,并且比迭代清楚是否采用递归,必须具体问题具体分析 间接递归 一个方法调用自身称作直接递归一个方法调用其他方法,最终导致再次调用自己,称作间接递归例如:方法m1调用m2,方法m2调用m3,方法m3又调用m1间接递归通常更难于追踪和调试 间接递归 m1 m2 m3 m1 m2 m3 m1 m2 m3 概要 递归思想递归编程使用递归解决问题图形程序中的递归用法 迷宫旅行 采用递归定义一条通过迷宫的路径每个位置,都可以在任意方法搜索递归追踪通过迷宫的路径基本事件就是无效的移动或者到达最终的目的地参考 MazeSearch.java (第397页)参考 Maze.java (第398页) Hanoi塔问题 Hanoi塔问题是经典的递归算法实例 此问题由3个竖立的塔座和一组中间有孔的圆盘组成圆盘直径不同, Hanoi塔的初始状态是所有的圆盘全部大小有序的叠放在一个塔座上,最大的盘子在最底层Hanoi塔问题的目标是将所有的圆盘从原始塔座上移动到到第三个塔座上,并且要满足以下规则:每次只能移动一个圆盘不能将大圆盘放到小圆盘的上面除非圆盘正处于在塔座间移动的过程中,否则所有圆盘必须在某个塔座上 Hanoi塔问题 初始状态 第一次移动 第三次移动 第二次移动 Hanoi塔问题 第四次移动 第五次移动 第六次移动 第七次移动 (完成) Hanoi塔问题 如果采用迭代解决方案将使问题更加复杂但是采用递归将使问题更加简洁参考 SolveTowers.java (第402页) 参考 TowersOfHanoi.java (第403页) 概要 递归思想递归编程使用递归解决问题图形程序中的递归用法 Fractals分形 分形是将相同模式的图案以不同的比例和方向构成的一个几何图形Koch雪花是 由一个等边三角形开始的特殊的一种分形为了获得更高阶的Koch 分形,使用尖角部分替换三角形边的中间部分的线段参考 KochSnowflake.java (第406页)参考 KochPanel.java (第408页) Koch 雪花