若一个对象部分地包含它自己

1、定义定义:若一个对象部分地包含它自己若一个对象部分地包含它自己, 或用或用它自己给自己定义它自己给自己定义, 则称这个对象是递归的；则称这个对象是递归的； 若一个过程直接地或间接地调用自己若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程则称这个过程是递归的过程。三种递归情况三种递归情况定义是递归的定义是递归的 数据结构是递归的数据结构是递归的 问题的解法是递归的问题的解法是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n- -1

2、);例如，阶乘函数例如，阶乘函数时时当当时时当当 1 ,)!1( 0 , 1!nnnnn求解阶乘求解阶乘 n! 的过程的过程 main : fact(4)参数参数 4 计算计算 4*fact(3) 返回返回 24参数参数 3 计算计算 3*fact(2) 返回返回 6参数参数 2 计算计算 2*fact(1) 返回返回 2参数参数 1 计算计算 1*fact(0) 返回返回 1参数参数 0 直接定值直接定值 = 1 返回返回 1参参数数传传递递结结果果返返回回有若干结点的单链表有若干结点的单链表例如，单链表结构例如，单链表结构f f 只有一个结点的单链表只有一个结点的单链表例例1.1.搜索链表

3、最后一个结点并打印其数值搜索链表最后一个结点并打印其数值void Search ( ListNode *f ) if ( f -next = NULL ) printf (“%dn”, f -data ); else Search ( f -next );f f f f f a0a1a2a3a4递归找链尾例例2.在链表中寻找等于给定值的结点在链表中寻找等于给定值的结点,并打印其数值并打印其数值void Search ( ListNode * f, ListData x ) if ( f ! = NULL ) if ( f - data = x ) printf (“%dn”, f -data

4、); else Search ( f - next, x );递归找含x值的结点f f f f x例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题的解法：问题的解法： 如果如果 n = 1，则将这一个盘子直接从，则将这一个盘子直接从 X 柱柱移到移到 Z柱上。否则，执行以下三步：柱上。否则，执行以下三步： 用用 Z 柱做过渡，将柱做过渡，将 X 柱上的柱上的 (n- -1) 个盘子移个盘子移到到 Y 柱上：柱上： 将将 X 柱上最后一个盘子直接移到柱上最后一个盘子直接移到 Z 柱上；柱上； 用用 X 柱做过渡，将柱做过渡，将 Y 柱上的柱上的 (n- -1) 个盘子移个盘子移到到

5、Z 柱上。柱上。算法算法void hanoi (int n, char X, char Y, char Z) /解决汉诺塔问题的算法 if ( n = 1 ) printf ( move %s,X, to %s”,Z); else Hanoi ( n-1, X, Z, Y ); printf ( move %s,X, to %s”,Z); Hanoi ( n-1, Y, X, Z ); n递归方法是设计非数值计算程序的重要方法，它使得程序的结构清晰，形式简洁，易于阅读，正确性容易证明。n一般地讲，一个问题采用递归算法求解时，须具备3个条件。 (1)能将一个问题转变成一个新问题，而新问题与原问题

6、的解法相同或类同，所不同的仅是所处理的对象，且这些处理对象的变化是有规律的。 (2)可以通过上述转化使问题逐步简单化。 (3)必须有一个明确的递归出口(递归的边界)。n递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。n层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反： 递归调用递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序n递归函数运行的递归函数运行的“层次层次”n函数嵌套调用时的函数嵌套调用时的“后调用先返回后调用先返回”原则原则n递归函数调用也是一种嵌套调用；每一次递归调用时，递归函数调用也是一种嵌套调用；每一次递

7、归调用时，也需要分配存储空间（工作区）来存储参数、局部变也需要分配存储空间（工作区）来存储参数、局部变量、返回地址等信息。量、返回地址等信息。n每层递归调用需分配的空间形成每层递归调用需分配的空间形成递归工作记录递归工作记录，按后，按后进先出进先出(LIFO)的栈组织。的栈组织。 局部变量局部变量返回地址返回地址参参 数数活动活动记录记录框架框架递归递归工作记录工作记录.Function() .调用块函数块n递归过程简洁、易编、易懂递归过程简洁、易编、易懂n递归过程效率低，重复计算多递归过程效率低，重复计算多n改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率n单向递归和尾递归可直接

8、用迭代实现其单向递归和尾递归可直接用迭代实现其非递归过程非递归过程n其他情形必须借助栈实现非递归过程其他情形必须借助栈实现非递归过程计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n- -1) + Fib (n- -2); 1n2),Fib(n1)Fib(n0,1nn,)Fib(n如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 Fib(1)Fib(0)

9、Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)n tagtag = 1, 向左递归向左递归；tag = 2, 向右递归向右递归Long FibIter(long n) if (n =1) return n; long twoback=0,oneback=1,current; for (int I=2;Idata = e; p-next = NULL; Q.rear-next =

10、p; /入队 Q.rear =p; return OK;出队出队int DeQueue ( LinkQueue &Q, QElemType &e) /删去队头结点，并返回队头元素的值 if ( Q.front=Q.rear ) return ERROR; /判队空 p = Q.front -next; e = p-data;/保存队头的值 Q.front-next = p-next; /新队头 if (Q.rear = p) Q.rear = Q.front ; free (p); return OK;循环队列循环队列 (Circular Queue)顺序队列顺序队列队列的顺序

11、存储表示队列的顺序存储表示 插入新的队尾元素，尾指针增插入新的队尾元素，尾指针增1，rear = rear + 1，删除队头元素，头指针增删除队头元素，头指针增1， front = front + 1，因此，在非空队列中，头指针始终指向队列头因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个元素，而尾指针始终指向队列尾元素的下一个位置。位置。 队满时再进队将溢出队满时再进队将溢出 假溢出（图假溢出（图3.12) 解决办法：将顺序队列解决办法：将顺序队列臆造臆造为一个环状的空间，为一个环状的空间，形成循环形成循环(环形环形)队列队列队列的进队和出队队列的进队和出队f

12、rontrear空队列空队列frontrearA,B,C, D进队进队A B C DfrontrearA,B出队出队C DfrontrearE,F,G进队进队C D E F GC D E F GfrontrearH进队进队,溢出溢出循环队列循环队列 (Circular Queue)队头、队尾指针加队头、队尾指针加1，可用取模，可用取模(余数余数)运算实现。运算实现。队头指针进队头指针进1: front = (front+1) %maxsize;队尾指针进队尾指针进1: rear = (rear+1) % maxsize;队列初始化队列初始化：front = rear = 0;队空条件队空条件：

13、front = rear;队满条件：队满条件：(rear+1) % maxsize = front;01234567循环队列循环队列frontrearMaxsize-101234567frontBCDrear一般情况一般情况A01234567rear空队列空队列front队满条件：队满条件：(rear+1) % maxsize = frontC01234567frontrearDEFGABC队满队满C01234567frontrearDEFGABCH#define MAXSIZE 100Typedef structQElemType *base;int front;int rear; SqQu

14、eue;循环队列的类型定义循环队列的类型定义初始化队列初始化队列Status InitQueue ( SqQueue &Q ) /构造空队列 Q.base=(QElemType *) malloc (MAXSIZE*sizeof(QElemType); if (! Q.base) exit(OVERFLOW); Q.rear = Q.front = 0; return OK;入队入队Status EnQueue ( SqQueue &Q, QElemType e ) if ( (Q.rear+1) % MAXSIZE =Q.front) return ERROR; /队满 Q.baseQ.rear = e; Q.rear = ( Q.rear+1) % MAXSIZE; return OK;出队出队Status DeQueue ( SqQueue &Q, QElemType &e ) if ( Q.front = Q.rear ) return ERROR; /队空 e = Q.baseQ.front; Q.front = ( Q.front+1) % MAXSIZE;return OK;n银行业务模拟程序 模拟银行业务活动并计算一天中客户在银行平均逗留时间n事件驱动模拟按事件（客