递归算法.ppt

算法设计和分析递归算法递归算法(Recursion) ?本章内容?递归算法的实现机制?递归化为非递归(难点)?递归算法举例?递归算法复杂性的计算(重点和难点) 递归算法算法设计和分析递归算法递归(Recursion) 定义?直接或间接地调用自身的算法称为递归算法?直接或间接调用自身的函数称为递归函数?尾递归是指递归调用的语句在递归函数的最后一句?递归算法的特点: 用于解决一类递归定义的问题算法易于实现,简单明了递归算法算法设计和分析递归算法 ?递归算法通过子程序/函数来实现子程序调用的形式参数传递和返回值的传送子程序调用的内部操作递归算法的实现机制算法设计和分析递归算法 子程序的调用形式递归算法的实现机制主程序主程序 Call A Call A 1: 1:…………子程序子程序 A A一次调用一次调用主程序主程序 Call A Call A 1: 1:………… Call A Call A 2: 2:…………子程序子程序 A A多次调用多次调用… 1 STACK … 1/2 STACK 算法设计和分析递归算法主程序主程序 Call A Call A 1: 1:…………子程序子程序 A A Call B Call B 2: 2:……子程序子程序 B B嵌套调用嵌套调用子程序子程序 A A 主程序主程序 Call B Call B 1: 1:…………子程序子程序 B B Call A Call A 2: 2:……平行调用平行调用递归算法的实现机制… 1 2 STACK … 1 2 STACK 算法设计和分析递归算法子程序/函数调用形式?关键: 用栈保存返回地址用寄存器保存返回地址(某些嵌入式处理器) 递归算法的实现机制算法设计和分析递归算法 参数传递和返回值的回传?参数传递按值的传送(值调用)按地址的传送(引用调用) ?两次值的传送?地址的传送?函数的返回值通过寄存器传递(AX/EAX) 通过全局变量的传送?例如 C++ 中的引用类型,一些脚本语言的引用变量类型都是按地址传送的例子递归算法的实现机制算法设计和分析递归算法参数的传递?值参数(value parameter) 用于输入参数的传递。一个值参数相当于一个局部变量, 只是它的初始值来自为该形参传递的实参。对值参数的修改不影响为该形参传递的实参。?引用参数(reference parameter) 用于输入和输出参数传递。引用参数与实参变量表示同一存储位置,对值参数的修改直接影响为该形参传递的实参。递归算法的实现机制算法设计和分析递归算法 子程序调用的内部操作? Caller: ( 主调函数) 在栈顶为形式参数开辟空间计算实参值并赋给栈顶的形参返回地址入栈指令流转向被调函数的入口? Callee :(被调函数) 初始化: ?局部量保存在堆栈中?从堆栈中取出形参运算返回: ?将返回值保存到回传变量中?从栈中取出返回地址?指令流转到返回地址处继续执行程序递归算法的实现机制算法设计和分析递归算法 递归程序的内部实现?内部实现和函数调用类似,代码只有一份?优点:简单明了结构清晰,可读性强容易用数学归纳法来证明算法的正确性?缺点: 运行效率较低入/出栈次数多,影响计算时间对系统栈的空间占用大,递归层次多时,容易导致栈溢出同一个函数多次的重复调用,开销大递归算法的实现机制