1、1/44Essential of Lecture Six ：一、递归 二、汉诺塔问题 三、递归与非递归的转化难点2/44一、递归一、递归 递归是程序设计中最有力的方法之一。递归是程序设计中最有力的方法之一。 优点： 采用 递归递归 编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。 问题：问题： 编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？3/44一、递归一、递归 递归递归 : 在定义自身的同时又出现了对自身的调用。 直接递归函数直接递归函数 :如果一个函数在其定义体内直接调用自己，则称直接递归函数。 间接递归函数
2、：间接递归函数： 如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数 。4/44 数学中常常利用递归手段来定义一些概念，如求阶乘的运算。 n的阶乘定义为：n * ( n 1 ) ! n0n! = 1 n=0例如 : 显然，该递归的出口是 0! =1。5/44 求阶乘的算法如下：求阶乘的算法如下：long fac (int n) long p;if (n=0| n=1) p=1;else p=n*fac(n-1) ;return p;void main()long x=fac(5);coutx;6/44 求阶乘的算法如下：求阶乘的算法如下：long fac (int
3、 n) long p;if (n=0 | n=1) p=1;else p=n*fac(n-1) ;return p; 递归函数包含：1、 递归调用语句 ，如 fac (n-1)；2、 基值判断 ，如 n=0 | n=1即为基值，保证了递归可以终止，满足基值条件后的计算 p=1, 一般称为最终计算；3、 调用之后的返回处理 。如 p= n * fac (n-1) ，是返回之后要进行的操作。7/44fac(5)main()n=5p=5*fac(4)第一层 facn=4p=4*fac(3)第二层 facn=3p=3*fac(2)第三层 facn=2p=2*fac(1)第四层 facn=1p=1第五层
4、 facfac(2)=2 fac(1)=1fac(3)=6fac(4)=24fac(5)=120输出假设调用该递归函数的 主函数为 第 0层 ，则从主函数调用递归函数为进入 第 1层 ；从第 i层递归调用本身为进入“下一层 ”，即 第 i+1 层 。反之，退出第 i 层递归应返回至 “上一层 ”，即第 i-1 层。递归层次 :8/44为了保证递归函数正确执行，系统需设立一个 “递归工作栈 ”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个 “工作记录 ”，其中包括所有的实参、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录 压入 栈顶。每退出一层递
5、归就从栈顶 弹出 一个工作记录，则当前执行层的工作记录必须是递归工作栈栈顶的工作记录，称这个记录为 “活动记录 ”，并称指示活动记录的栈顶指针为 “当前环境指针 ”。递归工作栈递归工作栈9/44分治算法分治算法分治算法 与软件设计的模块化方法类似。为了解决一个大的问题，将一个规模为 n的问题分解为规模较小的 子问题 ，这些子问题互相独立并且和原问题相同。分别解这些子问题 ，最后将将各个子问题的解合并得到原问题 的解。子问题通常与原问题相似，可以 递归地使用 分治策略 来解决 。 设计递归算法的方法 递归算法就是在算法中直接或间接调用算法本身的算法。 使用递归算法的前提有两个： 规模最小的子问题具有直接解。 原问题可以层层分解为类似的的子问题，且子问题比原问题的规模更小。设计递归算法的方法 寻找分解方法 设计递归出口 10/44
