递归-数据结构.ppt

* * 第6章 递归 6.3 递归算法的设计 6.1 什么是递归 6.2 递归调用的实现原理 本章小结 6.1 什么是递归 6.1.1 递归的定义 在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。 例6.1 以下是求n!(n为正整数)的递归函数。 int fun(int n) { if (n==1) /*语句1*/ return 1; /*语句2*/ else /*语句3*/ return ( fun(n-1)*n ); /*语句4*/ } 在该函数fun(n)求解过程中,直接调用fun(n-1)(语句4)自身,所以它是一个直接递归函数。又由于递归调用是最后一条语句,所以它又属于尾递归。 6.1.2 何时使用递归 在以下三种情况下,常常要用到递归的方法。 1. 定义是递归的 有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。 2. 数据结构是递归的 有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。 对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下： int Sum(LinkList *head) { if (head==NULL) return 0; else return(head-data+Sum(head-next)); } 3. 问题的求解方法是递归的 有些问题的解法是递归的,典型的有Hanoi问题求解. 该问题描述是：设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,…,n的盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法。 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上,递归分解的过程是： Hanoi(n,x,y,z) Hanoi(n-1,x,z,y)； move(n,x,z):将第n个圆盘从x移到z； Hanoi(n-1,y,x,z) Hanoi问题的递归算法 void Hanoi(int n, char x, char y, char z) //将n个盘片从x柱 通过y柱移动到z柱 { if (n==1) printf( “\t将第%d个盘片从%c柱移动到%c柱\n”, n, x, z ) ; else { hanoi( n-1, x, z, y ); printf(\t将第%d个盘片从%c柱移动到%c柱\n”, n, x, z ); hanoi( n-1, y, x, z ); } 主函数： int main( ) { int n; cout“输入盘片数n=”; cinn; Hanoi(n, ‘A’, ‘B’, ‘C’); return 0; } 6.1.3 递归模型 递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下： fun(1)=1 (1