计算机算法基础(第3递归算法

《计算机算法基础(第3递归算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归算法(Recursion)本章内容递归算法的实现机制递归化为非递归(难点)递归算法举例递归算法复杂性的计算(重点和难点)递归算法递归(Recursion)定义直接或间接地调用自身的算法称为递归算法直接或间接调用自身的函数称为递归函数尾递归是指递归调用的语句在递归函数的最后一句递归算法的特点：用于解决一类递归定义的问题算法易于实现，简单明了递归算法3.1递归算法的实现机制递归算法通过子程序/函数来实现子程序调用的形式参数传递和返回值的传送子程序调用的内部操作递归算法的实现机制1子程序的调用形式递归算法的实现机制主程序

2、CallA1:……子程序A一次调用主程序CallA1:……CallA2:……子程序A多次调用…1STACK…1/2STACK主程序CallA1:……子程序ACallB2:…子程序B嵌套调用子程序A主程序CallB1:……子程序BCallA2:…平行调用递归算法的实现机制…12STACK…12STACK子程序/函数调用形式关键：用栈保存返回地址用寄存器保存返回地址(某些嵌入式处理器)递归算法的实现机制2参数传递和返回值的回传参数传递按值的传送(值调用)按地址的传送(引用调用)两次值的传送地址的传送函数的返回值通过寄存器传

3、递(AX/EAX)通过全局变量的传送例如C++中的引用类型，一些脚本语言的引用变量类型都是按地址传送的例子递归算法的实现机制参数的传递值参数(valueparameter)用于输入参数的传递。一个值参数相当于一个局部变量，只是它的初始值来自为该形参传递的实参。对值参数的修改不影响为该形参传递的实参。引用参数(referenceparameter)用于输入和输出参数传递。引用参数与实参变量表示同一存储位置，对值参数的修改直接影响为该形参传递的实参。递归算法的实现机制函数参数和函数的值1函数间的按值传递在定义函数时函数名后

4、面括弧中的变量名称为“形式参数”(简称“形参”)，在主函数中调用一个函数时，函数名后面括弧中的参数(或表达式)称为“实际参数”(简称“实参”)。return后面的括弧中的值称为函数返回值例1调用函数时的数值传递#include“iostream.h”voidmain(){intx=5,y=10;swap(x,y);cout<

5、a=10b=5x=5y=10main函数在调用swap函数形式参数为a和b，实际参数为x和y，各自有不同的内存单元a和b交换时，并不能影响x和y的值。这是按值传递的特性2函数间的地址传递#include“iostream.h”voidmain(){intx=5,y=10;swap(&x,&y);cout<

6、b=5x=10y=5main函数在调用swap函数时，参数加了取地址运算符&，表示变量x和y的内存地址。形式参数为*a和*b，表示a和b是指针变量，*a和*b分别是指针a和b的内容。3函数间的引用传递#include“iostream.h”voidmain(){intx=5,y=10;swap(x,y);cout<

7、0b=5x=10y=5形式参数为&a和&b，即引用形式参数对引用形式参数的操作即对实际参数本身的操作3子程序调用的内部操作Caller:(主调函数)在栈顶为形式参数开辟空间计算实参值并赋给栈顶的形参返回地址入栈指令流转向被调函数的入口Callee:(被调函数)初始化：局部量保存在堆栈中从堆栈中取出形参运算返回：将返回值保存到回传变量中从栈中取出返回地址指令流转到返回地址处继续执行程序递归算法的实现机制递归程序的内部实现内部实现和函数调用类似，代码只有一份优点：简单明了结构清晰，可读性强容易用数学归纳法来证明算法的正确性

8、缺点：运行效率较低入/出栈次数多，影响计算时间对系统栈的空间占用大，递归层次多时，容易导致栈溢出同一个函数多次的重复调用，开销大递归算法的实现机制3.2递归化为非递归直接递归化为非递归(迭代)原则：在过程的开始部分，初始化用户栈(替代系统栈)，增加一个全局变量retvalue用于保存返回值建立标号：分别在过程的第一条可执行语句处、