递归（recurve）的概念汉诺塔（towerofhanoi）问题递归过

《递归（recurve）的概念汉诺塔（towerofhanoi）问题递归过》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归(Recurve)的概念汉诺塔(TowerofHanoi)问题递归过程与递归工作栈广义表(GeneralLists)第四章递归6/19/20211递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。在以下三种情况下，常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的6/19/20212定义是递归的?求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elseretu

2、rnn*Factorial(n-1);}例如，阶乘函数6/19/20213求解阶乘n!的过程6/19/20214计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}6/19/20215数据结构是递归的！搜索链表最后一个结点并打印其数值voidFind(ListNode*f){if(f→link==NULL)cout<

3、结构6/19/20216在链表中寻找等于给定值的结点并打印其数值voidPrint(ListNode*f){if(f!=NULL)if(f→data==x)cout<voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法if(n==1)cout<<"move"<

4、<"to"<>ch;if(ch!=‘.’){reverse;cout<

5、参数、局部变量等另外分配存储空间。层层向下递归，退出时的次序正好相反：递归次序n!(n-1)!(n-2)!1!0!=1返回次序因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。6/19/202111函数递归时的活动记录6/19/202112longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);RetLoc2returntemp;}voidmain(){intn;n=Factorial(4);RetLoc1}6/19/20

6、2113计算Factorial时活动记录的内容6/19/202114调用次数NumCall(k)=2*Fib(k+1)-1。斐波那契数列的递归调用树6/19/202115打印数组A[n]的值voidrecfunc(intA[],intn){if(n>=0){cout<=0){cout<<"value"<

7、endl;n--;}}6/19/202117广义表(GeneralLists)广义表的概念n(0)个表元素组成的有限序列，记作LS=(a0,a1,a2,…,an-1)LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。n>0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。6/19/202118广义表的特性有次序性有长度有深度可递归可共享A=()B=(6,2)C=(‘a’,(5,3,‘x’))D=(B,C

8、,A)E=(B,D)F=(4,F)6/19/202119各种广义表的示意图6/19/202120广义表的表示只包括整数和字符型数据的广义表链表表示表中套表情形下的广义表链表表示6/19/202121广义表结点定义标志域utype,表明结点类型。0为表头结点，1为整型原子结点，2为字符型原子