CH6递归.ppt

第六章递归 递归的定义递归中的参数传递递归的实例 一 递归的定义 1 定义 简单地说 就是子程序或函数重复调用自己 并传入不同的参数值来执行的一种程序设计方法 2 以下三种情况常常用到递归方法 定义是递归的数据结构是递归的问题的解法是递归的 1 调用前 1 将所有的实参 返回地址传递给被调用函数保存 2 为被调用函数的局部变量分配存储区 3 将控制转移到被调用函数入口 调用后 1 保存被调用函数的计算结果 2 释放被调用函数的数据区 3 依照被调用函数保存的返回地址将控制转移到调用函数 二 函数调用的过程 多个函数嵌套调用时 按照 后调用先返回 的原则进行 intmain intm n first m n 1 intfirst ints intt inti second i 2 intsecond intd intx y 3 2 函数调用过程 在C语言中 一般采用堆栈这上数据结构来记录函数调用后的返回地址 即 当主函数执行到first m n 时 堆栈需记录下一行程序语句的地址 以便在first m n 执行完后 能顺利返回主程序中继续执行未执行的程序语句 其他类推 intmain intm n inti intx y 3 2 1 3 函数嵌套调用过程示例 4函数的递归调用intf x intx inty z z f y return 2 z f函数调用f函数 例1 阶乘函数 三 递归的实例 1 定义是递归的 longfact longn longy if n 0 y 1 elsey n fact n 1 returny 求解阶乘函数的递归算法 01020304050607 includemain longx k scanf ld 010203040506070809101112131415 一个完整的求阶乘的程序 求解阶乘n 的过程 主程序main fact 4 参数4计算4 fact 3 返回24 参数3计算3 fact 2 返回6 参数2计算2 fact 1 返回2 参数1计算1 fact 0 返回1 参数0直接定值 1返回1 参数传递 结果返回 递归调用 回归求值 分析 1 了解题意是否适合用递归来解 2 决定递归结束条件 3 决定递归执行部分 4 例1中每次执行的过程相似 唯一的不同点为其中一个传入参数 每次执行都递减 递归结束条件n为0时返回其阶乘的值 否则继续调用程序并递减传入参数值 5 处理递归问题 常采用if语句来判断是否符合递归结束条件 其格式如下 if 符合递归结束条件 递归结束的结果 else递归执行部分 例2 费氏级数 FibonacciNumbers 问题 程序构思 递归结束条件 当n1时 返回费氏级数值为Fib n 1 Fib n 2 includemain intnum result scanf ld 010203040506070809101112131415 2 数据结构是递归的 一个结点 它的指针域为NULL 是一个单链表 一个结点 它的指针域指向单链表 仍是一个单链表 例如 单链表结构 f f 搜索链表最后一个结点并打印其数值voidPrint ListNode f if f next NULL printf d n f data elsePrint f next f f f f f a0 a1 a2 a3 a4 递归找链尾 在链表中寻找等于给定值的结点并打印其数值voidPrint ListNode f ListData f f f f 递归找含x值的结点 x 例1 汉诺塔 TowerofHanoi 问题 3 问题的解法是递归的 有三根木桩分别为A B C 有n个铁盘由小到大的放置在A木桩上 现需要将A木桩上的n个盘借助B木桩移到C木桩上 且必须遵守 一次只能移动一个盘子 每根木桩必须维持小盘在上 大盘在下的原则 汉诺塔 TowerofHanoi 问题的解法 如果n 1 则将这一个盘子直接从A柱移到C柱上 否则 执行以下三步 用C柱做过渡 将A柱上的 n 1 个盘子移到B柱上 将A柱上最后一个盘子直接移到C柱上 用A柱做过渡 将B柱上的 n 1 个盘子移到C柱上 voidHanoi intn charx chary charz if n 1 printf Movedisk dfrom cto c n x z else Hanoi n 1 x z y printf Movedisk dfrom cto c n x z Hanoi n 1 y x z 汉诺塔问题的递归算法 0102030405060708091011 includevoidHanoi intn charx chary charz if n 1 printf Movedisk dfrom cto c n x z else Hanoi n 1 x z y printf Movedisk dfrom cto c n x z Hanoi n 1 y x z voidmain intnum charone two three scanf d 0102030405060708091011121314151617181920 递归层次 运行语句序号 递归工作栈状态 返址 盘号 x y z 塔与圆盘的状态 1 2 3 2 1 2 4 5 1 2 4 5 1 2 3 9 6 7 汉诺塔问题的递归调用过程 递归层次 运行语句序号 递归工作栈状态 返址 盘号 x y z 塔与圆盘的状态 3 2 1 2 1 2 3 9 8 9 6 7 1 2 4 5 递归层次 运行语句序号 递归工作栈状态 返址 盘号 x y z 塔与圆盘的状态 3 2 3 2 1 2 3 9 6 7 1 2 3 9 8 9 递归层次 运行语句序号 递归工作栈状态 返址 盘号 x y z 塔与圆盘的状态 1 0 8 9 栈空 例2 迷宫问题 a 迷宫的图形表示 b 迷宫的二维数组表示 求解迷宫问题的简单方法是 从入口出发 沿某一方向进行探索 若能走通 则继续向前走 否则沿原路返回 换一方向再进行探索 直到所有可能的通路都探索到为止 为避免走回到已经进入的点 包括已在当前路径上的点和曾经在当前路径上的点 凡是进入过的点都应做上记号 为了记录当前位置以及在该位置上所选的方向 算法中设置了一个栈 栈中每个元素包括三项 分别记录当前位置的行坐标 列坐标以及在该位置上所选的方向 即directon数组的下标值 栈用顺序存储结构实现 栈中元素的说明如下 structNodeMaze intx y d typedefstructNodeMazeDataType 算法4 15求迷宫中一条路径的算法voidmazePath int maze int direction intx1 inty1 intx2 inty2 迷宫maze M N 中求从入口maze x1 y1 到出口maze x2 y2 的一条路径 其中1 x1 x2 M 2 1 y1 y2 N 2 inti j k kk intg h PSeqStackst DataTypeelement st createEmptyStack seq maze x1 y1 2 从入口开始进入 作标记 element x x1 element y y1 element d 1 push seq st element 入口点进栈 while notisEmptyStack seq st 走不通时 一步步回退 element top seq st i element x j element y k element d 1 pop seq st while kt kk printf the dnodeis d d n kk st s kk x st s kk y printf the dnodeis d d n kk i j printf the dnodeis d d n kk 1 g h return if maze g h 0 走到没走过的点 maze g h 2 作标记 element x i eleme