递归程序设计Java中一个方法调用自身称作递归方法递归方法的代码.PPT

第11章 递归 概要 递归思想 递归定义是以一种事物自身定义自身的过程 当定义一个英文单词时，递归定义通常没有帮助 但是有些场合，递归定义却是一个一种表达概念的恰当方法 在应用递归来编程前，培养递归思想是最好的方法 递归定义 考虑下面的数字列表: 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 概要 递归程序设计 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; } 递归程序设计 递归程序设计 需要注意的是，如果可以采用递归解决一个问题，并不意味着我们就应该采用递归取解决它 例如，我们不应该采用递归取解决1～N的求和计算问题，因为循环迭代求和的方法更易于理解 然而，对于其他一些问题，递归提供了一种简洁的解决方法，并且比迭代清楚 是否采用递归，必须具体问题具体分析 间接递归 一个方法调用自身称作直接递归 一个方法调用其他方法，最终导致再次调用自己，称作间接递归 例如：方法m1调用m2，方法m2调用m3，方法m3又调用m1 间接递归通常更难于追踪和调试 间接递归 概要 迷宫旅行 采用递归定义一条通过迷宫的路径 每个位置，都可以在任意方法有哪些信誉好的足球投注网站 递归追踪通过迷宫的路径 基本事件就是无效的移动或者到达最终的目的地 参考 MazeSearch.java (第397页) 参考 Maze.java (第398页) Hanoi塔问题 Hanoi塔问题是经典的递归算法实例 此问题由3个竖立的塔座和一组中间有孔的圆盘组成 圆盘直径不同， Hanoi塔的初始状态是所有的圆盘全部大小有序的叠放在一个塔座上，最大的盘子在最底层 Hanoi塔问题的目标是将所有的圆盘从原始塔座上移动到到第三个塔座上，并且要满足以下规则： 每次只能移动一个圆盘 不能将大圆盘放到小圆盘的上面 除非圆盘正处于在塔座间移动的过程中，否则所有圆盘必须在某个塔座上 Hanoi塔问题 Hanoi塔问题 Hanoi塔问题 如果采用迭代解决方案将使问题更加复杂 但是采用递归将使问题更加简洁 参考 SolveTowers.java (第402页) 参考 TowersOfHanoi.java (第403页) 概要 Fractals分形 分形是将相同模式的图案以不同的比例和方向构成的一个几何图形 Koch雪花是 由一个等边三角形开始的特殊的一种分形 为了获得更高阶的