数据结构 刘大有 第六章_递归1012.ppt

递归算法的实现 堆栈　保存四元组　(m,i,j,k) HR（m-l，i，k，j） ． MOVE（i，k） ． HR（m-l，j，i，k） S?（m-1，j，i，k）. S?（l，i，j，k） ． S?（m-1，i，k，j） Hanoi塔的迭代算法，m 是原柱上圆盘的个数 算法HI（m） HI1[建立堆栈] CREATS（S）． HI2[堆栈初始化] S?（m，1，2，3）． HI3[利用栈实现递归] WHILE NOT（StackEmpty（S））DO （（n,i,j,k） ?S． IF n = 1 THEN MOVE（i,k） ELSE（S?(n-1,j,i,k). S?(l,i,j,k)． S?(n-1,i,k,j)) ▌ 问题1：m个盘子的Hanoi塔问题，需移动多少次盘子？ 即HI的时间复杂性是多少？ 问题2：HI(m)需要多大的堆栈空间？ 即HI的空间复杂性是多少？ * 《数据结构》国家精品课程 * 第六章 递 归 6.1 递归的概念 6.2 基本递归过程 6.3 递归过程的实现与堆栈 定义：如果一个对象部分地包含它自己，或者利用自己定义自己的方式来定义或描述，则称这个对象是递归的（递归定义）；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程（递归算法） 。 组成：递归部分、终止条件(递归出口) 6.1 递归的概念 递归的例子 xn=x*x*…*x*x （幂函数） P(1) = x 递归出口 P(n)=P(n-1) * x, n1 递归部分 S(n)=1+2+3+…+(n-1)+n S(1) = 1 递归出口 S(n)=S(n-1)+n, n1 递归部分 以下三种情况适于用递归求解问题： 问题的定义是递归的； 问题所涉及的数据结构是递归的； 问题的解法满足递归的性质。 1、问题的定义是递归的 阶乘函数、幂函数和斐波那契数列。 [例1] 阶乘函数的定义 求解阶乘函数的递归过程 long Factorial(long n) { if (n= =0) return 1; //递归终止条件 else return n * Factorial(n-1); }　　　　　　　　　　 //递归调用过程 [例2] 斐波那契数列Fib(n)的定义 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n = 1 ) return n;  else return Fib (n-1) + Fib (n-2); }  2、问题所涉及的数据结构是递归的 [例1]　单链表节点类的递归定义 template class T class Node { private: Node T * next; public: T data; … … } data next [例2]　单链表的递归定义 head=NULL 头指针为head的单链表的递归定义： （1）head指向一个空结点的数据结构是一个单链表 （2）head指向一个非空结点，该结点的指针域指向一个单链表，这样的数据结构是一个单链表。 72 45 … head 36 ∧ 头指针为p的单链表中搜索链表最后一个结点并打印其数值 template class T void Find (NodeT *p) { if ( p →next == NULL ) cout p →data endl; else Find ( p →next ); } 3、问题的解法满足递归的性质 递归求解的基本思想（分治策略