第11章 递归 张坤龙 zhangkl@tju.edu.cn 天津大学计算机学院
概要 递归思想 递归编程 使用递归解决问题 图形程序中的递归用法
递归思想 递归定义是以一种事物自身定义自身的过程 当定义一个英文单词时，递归定义通常没有帮助 但是有些场合，递归定义却是一个一种表达概念的恰当 方法 在应用递归来编程前，培养递归思想是最好的方法
递归定义 考虑下面的数字列表: 24, 88, 40, 37 这样的列表也能这样定义: 列表是: 一个数字 或者: 一个数字 , 列表 即, 列表定义尾一个数字或者一个数字后面跟一个逗号(，)再跟一个列表 列表的概念被用于定义列表自身
递归定义 列表定义的递归部分，使用了多次，最终以非递归部分结束: 数字 逗号 列表 24 , 88, 40, 37 88 , 40, 37 数字 逗号 列表 24 , 88, 40, 37 88 , 40, 37 数字 逗号 列表 40 , 37 数字 37
无穷递归 所有的递归定义都应该有非递归部分和递归部分构成 如果没有非递归部分，递归将无法终止 这样的定义就是无穷递归 非递归部分通常称作基本事件
递归定义 对于任何正整数N，N!(N的阶乘)的值定义为所有1～N （包括N）之间的所有整数的乘积 此定义的递归表达如下: 1! = 1 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 num public int sum (int num) { int result; if (num == 1) result = 1; else result = num + sum (n-1); return result; }
递归程序设计 main sum sum(3) sum(1) sum(2) result = 1 result = 3 result = 6
递归程序设计 需要注意的是，如果可以采用递归解决一个问题，并不 意味着我们就应该采用递归取解决它 例如，我们不应该采用递归取解决1～N的求和计算问 题，因为循环迭代求和的方法更易于理解 然而，对于其他一些问题，递归提供了一种简洁的解决 方法，并且比迭代清楚 是否采用递归，必须具体问题具体分析
间接递归 一个方法调用自身称作直接递归 一个方法调用其他方法，最终导致再次调用自己，称作 间接递归 例如：方法m1调用m2，方法m2调用m3，方法m3又 调用m1 间接递归通常更难于追踪和调试
间接递归 m1 m2 m3
概要 递归思想 递归编程 使用递归解决问题 图形程序中的递归用法
迷宫旅行 采用递归定义一条通过迷宫的路径 每个位置，都可以在任意方法搜索 递归追踪通过迷宫的路径 基本事件就是无效的移动或者到达最终的目的地 参考 MazeSearch.java (第397页) 参考 Maze.java (第398页)
Hanoi塔问题 Hanoi塔问题是经典的递归算法实例 此问题由3个竖立的塔座和一组中间有孔的圆盘组成 每次只能移动一个圆盘 不能将大圆盘放到小圆盘的上面 除非圆盘正处于在塔座间移动的过程中，否则所有圆盘必须在 某个塔座上
Hanoi塔问题 初始状态 第一次移动 第二次移动 第三次移动
Hanoi塔问题 第四次移动 第五次移动 第六次移动 第七次移动 (完成)
Hanoi塔问题 如果采用迭代解决方案将使问题更加复杂 但是采用递归将使问题更加简洁 参考 SolveTowers.java (第402页) 参考 TowersOfHanoi.java (第403页)
概要 递归思想 递归编程 使用递归解决问题 图形程序中的递归用法
Fractals分形 分形是将相同模式的图案以不同的比例和方向构成的一 个几何图形 Koch雪花是 由一个等边三角形开始的特殊的一种分形 参考 KochSnowflake.java (第406页) 参考 KochPanel.java (第408页)
Koch 雪花 < x5, y5> < x1, y1> < x5, y5> 变为
Koch 雪花
Koch雪花
本章小结 以递归模式思考 以递归模式编程 递归使用纠错 递归使用举例