PPT《第6章 递归》

第6章 递归 6.

3 递归算法的设计 6.1 什么是递归 6.2 递归调用的实现原理 本章小结 6.1.1 递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归.若调用自身,称之为直接递归.若函数p调用函数q,而q又调用p,称之为间接递归. 如果一个递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归. 6.1 什么是递归 例6.1 以下是求n!(n为正整数)的递归函数. int fun(int n)if (n==1) /*语句1*return 1;

/*语句2*else /*语句3*return fun(n-1)*n;

/*语句4*/}递归可以把一个大型复杂的问题转化为一个与原问题相似的规模较小的问题来求解,通过少量的语句,实现重复计算.体现了分而治之的算法思想 在以下3种情况下,常常要用到递归的方法.1. 定义是递归的2. 数据结构是递归的 例如,单链表就是一种递归的数据结构,其结点类型定义如下: typedef struct LNode ElemType data;

struct LNode *next;

LinkList;

该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针. 6.1.2 何时使用递归 求n!和Fibonacci数列 例:求一个不带头结点的单链表head的所有data域(假设为int型)之和. int Sum(LinkList *head)if (head==NULL)return 0;

else return(head->data+Sum(head->next) 汉诺塔问题是印度的一个古老的传说.在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽. 3. 问题的求解方法是递归的 Hanoi问题 n阶Hanoi塔问题:假设有三个分别命名为X,Y,Z的塔座,在X塔座上插有n个直径大小各不相同,依小到大编号为1,2,…,n的圆盘,要求:把X上的n个圆盘移到Z上,排列顺序相同,移动规则为:每次只能移动一个圆盘;

圆盘可以在任一塔上做多次移动;

在任何时刻,大盘不能压小盘;

X Y Z Hanoi问题 void Hanoi( int n, char x, char y, char z ){if( n ==

1 ) Move( 1, x, z );

// 把1号盘,从x移到zelse{ Hanoi( n C 1, x, z, y );

// 把n-1个盘,从x移到y,z为辅助塔Move( n, x, z );

// 把n号盘,从x移到zHanoi( n C 1, y, x, z );

//把n-1个盘,从y移到z,x为辅助塔 }} 以求n!为例,对应的递归模型如下: fun(1)=1 (1)fun(n)=n*fun(n-1) n>1 (2)(1)式给出了递归的终止条件,称为递归出口;

(2)式给出了fun(n)的值与fun(n-1)的值之间的关系,称为递归体. 6.1.3 递归模型 递归求n! n=3fuc(3) sreturn(3*fuc(2)) n=2fuc(2) s s sreturn(2*fuc(1)) n=1fuc(1){ if(n==1) return

1 s s } return fuc(3)=3*2*1 return fuc(2)=2*1 return fuc(1)=1 递归的实现过程类似于多层函数的嵌套调用,只是调用者和被调用者是同一个函数而已 原则:后调用先返回 分解过程 求值过程 int fun(int n)if (n==1)语句1*return 1;

语句2*else /*语句3*return fun(n-1)*n;

/*语句4*/} 递归调用的实现原理 递归工作栈是递归函数运行期间使用的数据存储区每一次递归调用时,需要将实在参数、返回地址等信息传递给被调用函数保存,并且要保存被中断函数本层的参数和局部变量,以便从下一层返回时重新使用;