数据结构数据结构 精品课程精品课程第六章第六章 递递 归归第一节第一节 递归的定义递归的定义第二节第二节 基本递归过程基本递归过程第三节第三节 递归过程实现与堆栈递归过程实现与堆栈第四节第四节 递归法求解问题递归法求解问题第五节第五节 递归的效率递归的效率第第 页页数据结构数据结构 精品课程精品课程线性表线性表第第 页页数据结构数据结构 精品课程精品课程栈和递归在程序设计中的应用是非常栈和递归在程序设计中的应用是非常广泛的，如对于迷宫的求解、表达式的广泛的，如对于迷宫的求解、表达式的求解等都可以用栈来解决。典型的求解等都可以用栈来解决。典型的hanoihanoi塔问题，树和图的遍历等都可以用递归塔问题，树和图的遍历等都可以用递归来解决。递归算法的设计实际上就是对来解决。递归算法的设计实际上就是对问题的抽象的过程，如果抽象到每个小问题的抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归，问题都有相同特征时，那就形成了递归，递归算法简明易懂。递归算法简明易懂。第第 页页数据结构数据结构 精品课程精品课程 递归不仅是数学中的一个重要概念，递归不仅是数学中的一个重要概念，也是计算技术中重要的概念之一。也是计算技术中重要的概念之一。20世世纪纪30年代，正是可计算的递归函数理论年代，正是可计算的递归函数理论与图灵机演算和与图灵机演算和POST规范系统等理论一规范系统等理论一起为计算理论的建立奠定了基础。起为计算理论的建立奠定了基础。第第 页页数据结构数据结构 精品课程精品课程从方法论意义上说，递归方法是一种从简从方法论意义上说，递归方法是一种从简单到复杂、从低级到高级的可连续操作的解决单到复杂、从低级到高级的可连续操作的解决问题的方法。问题的方法。在人们的思维过程中，普遍存在着递归现在人们的思维过程中，普遍存在着递归现象和递归机制。象和递归机制。对于某些问题，只能用递归方法来处理；对于某些问题，只能用递归方法来处理；对于某些问题，用递归方法处理比其他方法更对于某些问题，用递归方法处理比其他方法更有效。有效。第第 页页数据结构数据结构 精品课程精品课程6.1 什么是递归什么是递归 xn=x*x*x*x （n个个x连乘连乘）xn+1=xn*x S(n)=1+2+3+(n-1)+n S(n+1)=S(n)+(n+1)优点：优点：直观、有效直观、有效 第第 页页数据结构数据结构 精品课程精品课程定义：定义：如果一个对象部分地如果一个对象部分地包含包含它自己，它自己，或者利用自己定义自己的方式来定或者利用自己定义自己的方式来定义或描述，则称义或描述，则称这个对象这个对象是递归的；是递归的；如果一个过程如果一个过程直接或间接直接或间接地调用自地调用自己，则称这个己，则称这个过程是过程是一个递归过程。一个递归过程。组成：组成：递归调用、递归终止条件递归调用、递归终止条件第第 页页数据结构数据结构 精品课程精品课程以下三种情况适于用递归求解问题：以下三种情况适于用递归求解问题：1.问题的定义是递归的问题的定义是递归的2.问题所涉及的数据结构是递归的；问题所涉及的数据结构是递归的；3.问题的解法满足递归的性质。问题的解法满足递归的性质。第第 页页数据结构数据结构 精品课程精品课程1、问题的定义是递归的、问题的定义是递归的阶乘函数、幂函数阶乘函数、幂函数和和斐波那契数列。斐波那契数列。例例阶乘函数的定义阶乘函数的定义第第 页页数据结构数据结构 精品课程精品课程求解阶乘函数的递归过程求解阶乘函数的递归过程long Factorial(long n)if(n=0)return 1;/递归终止条件递归终止条件else return n*Factorial(n-1);/递归调用过程递归调用过程第第 页页数据结构数据结构 精品课程精品课程求解求解 4!的过程的过程第第 页页数据结构数据结构 精品课程精品课程计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法long Fib(long n)if(n=1)return n;else return Fib(n-1)+Fib(n-2);第第 页页数据结构数据结构 精品课程精品课程递归求解的过程：递归求解的过程：对于一个比较复杂的问题，如果能够对于一个比较复杂的问题，如果能够把它把它分解分解为若干个为若干个相对简单相对简单的、而且的、而且解法解法相同相同或或类似类似的子问题，那么当这些子问题的子问题，那么当这些子问题获得解决时，原问题就获得解决分治获得解决时，原问题就获得解决分治策略。策略。子问题无需分解就可以直接解决时，子问题无需分解就可以直接解决时，停止分解，直接求解该子问题停止分解，直接求解该子问题递归结递归结束条件。束条件。第第 页页数据结构数据结构 精品课程精品课程2、问题所涉及的数据结构是递归的例单链表 head=NULL7245head36第第 页页数据结构数据结构 精品课程精品课程在头指针为在头指针为p的单链表中搜索的单链表中搜索data值为值为item的结点的结点template void Search（Node *p，T item）if（p=NULL）cerr data=item）Dealwith（p）；）；/通过通过Dealwith函数对函数对该节点进行一定的处理该节点进行一定的处理elseSearch（p-next，item）；）；第第 页页数据结构数据结构 精品课程精品课程搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Find(Node*f)if(f next=NULL)cout f data endl;else Find(f next);第第 页页数据结构数据结构 精品课程精品课程二叉树：二叉树是数据元素的有穷二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉集合，它或者为空集（空二叉 树），或者由一个根元素和其下的两树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子棵互不相交的二叉树（左子树和右子树）构成。树）构成。第第 页页数据结构数据结构 精品课程精品课程3、问题的解法满足递归的性质例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题问题 问题的提出：问题的提出：在在19世纪末，布拉玛神庙世纪末，布拉玛神庙(Temple of Bramah)里的传教士玩着一种游戏，据说他们里的传教士玩着一种游戏，据说他们的游戏装置是由一块铜板上有三根金刚石针，针的游戏装置是由一块铜板上有三根金刚石针，针上放有上放有64个直径大小不等的金盘组成的。游戏的个直径大小不等的金盘组成的。游戏的目标是把左面针上的金盘移动到右面的针上，移目标是把左面针上的金盘移动到右面的针上，移动过程中一次只能移动一个盘子，不允许大盘放动过程中一次只能移动一个盘子，不允许大盘放在小盘上面，只能借助于中间的针。他们认为这在小盘上面，只能借助于中间的针。他们认为这种游戏的结束就意味着世界末日的到来。欧洲人种游戏的结束就意味着世界末日的到来。欧洲人把这种游戏叫做汉诺塔把这种游戏叫做汉诺塔(Tower of Hanoi)游戏。游戏。第第 页页数据结构数据结构 精品课程精品课程第第 页页数据结构数据结构 精品课程精品课程对于对于n阶汉诺塔进行一下分析：阶汉诺塔进行一下分析：1.把把n个盘子从上到下编号个盘子从上到下编号1n,要把要把n个盘子从个盘子从a塔移动到塔移动到c塔塔,首先借用首先借用b塔作为存放盘子的临时塔作为存放盘子的临时塔，把上面的塔，把上面的n-1个盘子移动到个盘子移动到b;2.把第把第n个盘子移动到个盘子移动到c3.那么如何把第那么如何把第n-1个盘子移动到个盘子移动到c？可以把可以把a作为临时塔，把第作为临时塔，把第n-1盘子上面的盘子上面的n-2个盘子从个盘子从b移动到移动到a，把第，把第n-2个盘子移动到个盘子移动到c。这。这样样n-2个盘子又回到了个盘子又回到了a上了。上了。4.以此类推，下面以此类推，下面n-2个盘子的移动仿佛是在重复个盘子的移动仿佛是在重复第第1、2步操作，这个问题变成了典型的递归问题。步操作，这个问题变成了典型的递归问题。第第 页页数据结构数据结构 精品课程精品课程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);cout move A to C endl;Hanoi(n-1,B,A,C);第第 页页数据结构数据结构 精品课程精品课程6.2基本递归过程基本递归过程 递归过程在实现时，发生递归调用：递归过程在实现时，发生递归调用：分为分为内部调用和外部调用内部调用和外部调用。调用方式不同，返回的方式也不相同。调用方式不同，返回的方式也不相同。v递归调用正确进行：调用时参数传递正递归调用正确进行：调用时参数传递正确确v过程结束正确返回：返回地址正确过程结束正确返回：返回地址正确第第 页页数据结构数据结构 精品课程精品课程在高级语言（编译程序）中，是利用在高级语言（编译程序）中，是利用“递归工作栈递归工作栈”来来实现递归调用的。实现递归调用的。f(n)f(n-1)f(n-2)f(1)f(0)调用时执行入栈操作保存现场，返回时执行出栈调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场操作恢复现场调用调用返回返回调用点调用点 PnPn-1Pn-2P11第第 页页数据结构数据结构 精品课程精品课程层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反：递归次序递归次序n!(n-1)!(n-2)!1!0!=1 返回次序返回次序工作记录：工作记录：返回地址返回地址参数参数（函数名、引用参数与数组参数等）（函数名、引用参数与数组参数等）局部变量局部变量第第 页页数据结构数据结构 精品课程精品课程函数递归时的活动记录函数递归时的活动记录第第 页页数据结构数据结构 精品课程精品课程 long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);RetLoc2 void main()int Result;Result=Factorial(4);RetLoc1 第第 页页数据结构数据结构 精品课程精品课程计算计算Factorial时活动记录的内容时活动记录的内容第第 页页数据结构数据结构 精品课程精品课程堆栈堆栈:递归算法转化为非递归算法递归算法转化为非递归算法CREATS(S)：建立一个堆栈：建立一个堆栈 S;S x :元素元素 x 进栈；进栈；x S:元素元素 x 出栈；出栈；StackEmpty(S):若若 S 为空，返回为空，返回1.最后一次发生的递归过程必须最先完成。最后一次发生的递归过程必须最先完成。6.3递归过程的实现：堆栈与递归递归过程的实现：堆栈与递归第第 页页数据结构数据结构 精品课程精品课程例例2.3 计算数组计算数组 A 中最大中最大最小元素的算法最小元素的算法BS。算法算法BS（A，i，j.fmax，fmin）/在数组在数组A的第的第i个元素到第个元素到第j个元素之间寻找最大个元素之间寻找最大和最小元素，已知和最小元素，已知i j。BS1 递归出口递归出口 IF i=j THEN（fmaxfminAi.RETURN.）IF i=j 1 THEN（IF Ai n THEN RETURN(0).ELSE IF(n=k OR k=0)THEN RETURN(1).COMM2递归调用递归调用RETURN(COMM(n-1,k)+COMM(n-1,k-1)第第 页页数据结构数据结构 精品课程精品课程递归的应用回溯递归的应用回溯(backtracking)寻找特定问题解的一种比较可靠的方法是首先列出寻找特定问题解的一种比较可靠的方法是首先列出所有候选解，然后依次检查每一个