递归算法.pptVIP

递归算法(Recursion) 本章内容 递归算法的实现机制 递归化为非递归(难点) 递归算法举例 递归算法复杂性的计算(重点和难点) 递归(Recursion)定义 直接或间接地调用自身的算法称为递归算法 直接或间接调用自身的函数称为递归函数 尾递归是指递归调用的语句在递归函数的最后一句 递归算法的特点： 用于解决一类递归定义的问题 算法易于实现，简单明了 1.递归算法的实现机制 递归算法通过子程序/函数来实现 子程序调用的形式 参数传递和返回值的传送 子程序调用的内部操作 1.1 子程序的调用形式 子程序/函数调用形式 关键： 用栈保存返回地址 用寄存器保存返回地址(某些嵌入式处理器) 1.2参数传递和返回值的回传 参数传递 按值的传送(值调用) 按地址的传送(引用调用) 两次值的传送 地址的传送 函数的返回值 通过寄存器传递(AX/EAX) 通过全局变量的传送 例如 C++中的引用类型，一些脚本语言的引用变量类型都是按地址传送的例子 参数的传递 值参数 (value parameter) 用于输入参数的传递。一个值参数相当于一个局部变量，只是它的初始值来自为该形参传递的实参。对值参数的修改不影响为该形参传递的实参。 引用参数 (reference parameter) 用于输入和输出参数传递。引用参数与实参变量表示同一存储位置，对值参数的修改直接影响为该形参传递的实参。 1.3子程序调用的内部操作 Caller: (主调函数) 在栈顶为形式参数开辟空间 计算实参值并赋给栈顶的形参 返回地址入栈 指令流转向被调函数的入口 Callee:(被调函数) 初始化： 局部量保存在堆栈中 从堆栈中取出形参运算 返回： 将返回值保存到回传变量中 从栈中取出返回地址 指令流转到返回地址处继续执行程序 1.4递归程序的内部实现 内部实现和函数调用类似，代码只有一份 优点：简单明了 结构清晰，可读性强 容易用数学归纳法来证明算法的正确性 缺点：运行效率较低 入/出栈次数多，影响计算时间 对系统栈的空间占用大，递归层次多时，容易导致栈溢出 同一个函数多次的重复调用，开销大 2.递归化为非递归 直接递归化为非递归(迭代) 原则： 在过程的开始部分，初始化用户栈(替代系统栈)，增加一个全局变量retvalue用于保存返回值 建立标号：分别在过程的第一条可执行语句处、每个递归调用处建立标号，依次为：L0,L1,L2,……，做为入口地址和返回地址 消去递归调用：局部变量、形参、返回地址入栈,形式参数赋值，goto语句到L0 修改函数的返回部分： 用户栈为空，返回 返回值保存到全局变量中，同时将引用参数赋给栈顶的相应变量 取出返回地址，恢复现场。(即恢复主调函数的局部量、参数等,注意栈的平衡) 转向返回地址处执行 GCD例 参数的传递可以不用stack 恢复现场后a,b不再使用，所以不用保护a,b 标号L0,L1,L2中, 栈里保存的不可能是L0,L1也可以去掉，于是栈里的返回地址总是L2, 返回地址也可以不用保存 参数res也不需要保存在栈里 用户栈就可以取消 3.递归算法设计 可用递归解决的问题P 问题P具有规模 不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成 小规模的问题是可解的 关键： 找到递归的递推关系 找到结束递归的条件 递归求解的伪代码 简单的0/1背包问题 Hanoi塔问题 棋子移动 n个元素的全排列 4.递归关系式的计算 递归算法时间复杂度的分析(重点) 递归算法时间复杂度的计算(难点) 4.1递归算法时间复杂度分析 根据递归算法思想，可以得到递归算法的时间复杂度的递推关系式 求解递推关系式即可 例：GCD T(a,b) = T(b,a%b) + C0, 其中C0为常数 最坏情况：T(a) = T(a/2) + C0 = O(logn) 4.2时间复杂度的计算-迭代法 作业 1.初值的判断： n=2, 0011_ _ → 0_ _ 101 →010_ _ 1 , 无解 n=3, 无解 n=4: 0 0 0 0 1 1 1 1 _ _ 0 0 0 _ _ 1 1 1 0 1 0 0 0 1 0 1 1 _ _ 1 0 _ _ 1 0 1 1 0 0 1 0 1 0 1 0 1 _ _ 0 1 _ _ 0 1 0 1 0 1 0 1 3.递归算法设计 2.递推关系式: 0 0 0 . . . 0 0 0 1 1 1 . . . 1 1 1 _ _ (n) 0 0 0 . . . 0 0 _ _ 1 1 . . . 1 1 1 0 1 0 0 0 . . . 0 0 1 1 1 1 . . . 1 _ _ 0 1 (n-1) 对n-1个棋子进行递归的移动直到n=4为止 3.递归算法设计 3.