第章递归.docVIP

第5章 递归和广义表 递归在计算机科学和数学中是一个很重要的工具，它在数据结构中用来解决表或树形结构的有哪些信誉好的足球投注网站和排序等问题，并可用于定义和实现广义表。 5.1 递归(Recurve)的概念 1．递归的定义是： 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的;而且若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。 2．在以下三种情况下，常常要用到递归的方法。 (1)定义是递归的; 数学上常用的阶乘函数、幂函数、斐波那契数列等，它们的定义和计算都是递归的。例如阶乘函数，它的定义是 对应这个递归的函数，我们可以使用递归过程来求解。 long Factorial(long n){ if ( n = = 0 ) return 1; //终止递归的条件 else return n *= Factorial ( n (1); //递归步骤 } 在这个程序中我们利用if…else…语句把递归结束条件与其它表示继续递归的情况区别开来。if语句块判断递归结束的条件，而else语句块处理递归的情况(当然也可以反过来使用)。 在计算n!时，if语句块判断唯一的递归结束条件n = =0，并返回值1; else语句块通过计算表达式n* (n-1)！并返回计算结果以完成递归。 可以得出以下三点认识： 1.对于一个较为复杂的问题，如果能够分解成几个相对简单的且解法相同或类似的子问题时，只要解决了这些子问题，那么原问题就迎刃而解了，这就是递归求解。这种分解一求解的策略叫做“分治法”。 2.当分解后的子问题可以直接解决时，就停止分解。我们把这些可以直接求解的问题叫做递归结束条件。 3.递归定义的函数可以简单地用递归过程来编程求解。递归过程直接反映了定义的结构。 (2)数据结构是递归的; 例如，链表就是一种递归的数据结构。 对于递归的数据结构，采用递归的方法来编写算法特别方便。例如，我们想找到非空单链表最后一个结点并打印其数据域的值，就可以使用递归形式的过程。 template class Typevoid Find(ListNode Type* f){ if(f-link = = NULL)cout f -data endl; else Find(f-link); } (3)问题的解法是递归的。 有些问题只能用递归方法来解决，一个典型的例子就是汉诺塔(Tower of Hanoi)问题。 利用这个解法，将移动n个盘子的汉诺塔问题归结为移动(n-1)个盘子的汉诺塔问题。与此类似，移动(n-1)个盘子的汉诺塔问题又可归结为移动(n一2)个盘子的汉诺塔问题，……，最后总可以归结到只移动一个盘子的汉诺塔问题，这样问题就解决了。 现在我们给出根据上述解法而得到的求解n阶汉诺塔问题的算法。 ＃include iostream. h # include strclass. h//字符串类的原型文件 void Hanoi ( int n，String A, String B, String C){ if ( n = = 1) cout “move” A“to” C endl; //一个盘子，直接移动 else{ Hanoi(n-1, A, C, B); //将上面n-1个盘子移到B柱 cout“move” A“to” C endl; //最后一个移到C柱} Hanoi(n-1, B, A, C); //将n-1个盘从B柱移到C柱 } } 5. 2 迷宫问题 1．利用递归方法获得迷宫从人口到出口的最佳路线。 本节我们利用迷宫(Maze)问题作为实例，讨论递归问题的求解方法。 为了求解迷宫问题，用到了回溯(backtracking)方法。当我们沿某一条路径一步步走向出口但发现进人死胡同走不通时，就回溯一步或多步，寻找其它可走的路径，这就是回溯的方法。以图5.4所示的迷宫为例，它实际上是一系列交通路口(Intersection)的集合。每个交通路口有3个相关联的参数，分别代表直走(正向走)、左拐弯和右拐弯，如果参数值等于0,表示该方向的路堵死;如果参数值不为0，表示该方向还有路可通。 Struct Intersection{ //从当前路口出发，按left, forward,right三个方向所用到的结构 int left; //左拐，堵死为0 int forward ; //直走，堵死为0 int right ; //右拐，堵死为0 } 在每个交通路口上，先试探着向左走，如果向左