递归函数和非递归函数的转变

1、第第6 6章章 递归递归 6.3 6.3 递归算法到非递归算法的转换递归算法到非递归算法的转换6.1 6.1 什么是递归什么是递归6.2 6.2 递归算法的设计递归算法的设计本章小结本章小结6.1 6.1 什么是递归什么是递归6.1.1 6.1.1 递归的定义递归的定义 在定义一个过程或函数时出现调用本过程或本在定义一个过程或函数时出现调用本过程或本函数的成分函数的成分, ,称之为称之为递归递归。若调用自身。若调用自身, ,称之为称之为直接直接递归递归。若过程或函数。若过程或函数p p调用过程或函数调用过程或函数q,q,而而q q又调用又调用p,p,称之为称之为间接递归间接递归。 例例 求求n

2、!(n为正整数为正整数) 。 一般的方法：一般的方法：n! = 1*2*(n-1)*n 递归的方法：递归的方法：时当时当 1 ,)!1( 0 , 1!nnnnn int factorial(int n) int x; if (n=0) x=1; else x=factorial (n-1)*n; return(x); 在该函数在该函数factorial (n)求解过程中求解过程中,直接调用直接调用factorial (n-1)自身自身,所以它是一个所以它是一个直接递归函数直接递归函数。 int factorial(int n) int x; if (n=0) x=1; else x=facto

3、rial (n-1)*n; return(x); n=4n=3n=2n=1n=06.1.2 6.1.2 何时使用递归何时使用递归 在以下三种情况下在以下三种情况下,常常要用到递归的方法。常常要用到递归的方法。 1. 定义定义是递归的是递归的 2. 数据结构数据结构是递归的是递归的 3. 问题的问题的求解方法求解方法是递归的是递归的 1. 定义是递归的定义是递归的 有许多有许多数学公式数学公式、数列数列等的定义是递归的。这些等的定义是递归的。这些问题的求解过程可以将其递归定义直接转化为对应问题的求解过程可以将其递归定义直接转化为对应的递归算法。的递归算法。 例如例如,求求Fibonacci数列数

4、列:1),2() 1(0,1,)(nnFibnFibnnnFib2. 数据结构是递归的数据结构是递归的 有些数据结构是递归的。例如有些数据结构是递归的。例如,第第2章中介绍过的单章中介绍过的单链表就是一种递归数据结构链表就是一种递归数据结构,其结点类型定义如下：其结点类型定义如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 对于递归数据结构对于递归数据结构,采用递归的方法编写算法既方采用递归的方法编写算法既方便又有效。例如便又有效。例如,求一个不带头结点的单链表求一个不带头结点的单链表head的所的所有有

5、data域域(假设为假设为int型型)之和的递归算法：之和的递归算法： int Sum(LinkList *head) if (head=NULL) return 0; else return (head-data+Sum(head-next); 3. 问题的求解方法是递归的问题的求解方法是递归的 有些问题的解法是递归的有些问题的解法是递归的,典型的有汉诺塔典型的有汉诺塔(Tower of Hanoi)问题求解：问题求解：盘片移动时必须遵守以下规则：盘片移动时必须遵守以下规则：每次只能移动一个盘片；每次只能移动一个盘片；盘片可以插在盘片可以插在A,B和和C中任一塔座；中任一塔座；不能将一个较大

6、的盘片放在较小的盘片上。不能将一个较大的盘片放在较小的盘片上。Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c)；Hanoi(n-1,b,a,c)6.1.3 6.1.3 递归模型递归模型 递归模型是递归算法的抽象递归模型是递归算法的抽象,它反映递归问题的它反映递归问题的递归结构递归结构,例如例如,前面的递归算法对应的递归模型如下：前面的递归算法对应的递归模型如下：fun(0)=1 n=0(1) fun(n)=n*fun(n-1)n0 (2) 其中：第一个式子给出了其中：第一个式子给出了递归的终止条件递归的终止条件,我们称我们称之为之为递归出口递归出口；第二个式

7、子给出了；第二个式子给出了fun(n)的值与的值与fun(n-1)的值之间的关系，我们的值之间的关系，我们称之为称之为递归体递归体。 一般地一般地,一个递归模型是由一个递归模型是由递归出口递归出口和和递归体递归体两部两部分组成分组成, 前者确定前者确定递归到何时结束递归到何时结束, 后者确定后者确定递归求解递归求解时的递推关系时的递推关系。递归出口递归出口的一般格式如下：的一般格式如下： f(s1)=m1 (6.1) 这里的这里的s1与与m1均为常量均为常量,有些递归问题有些递归问题可能有几个可能有几个递归递归出口。出口。 递归体递归体的一般格式如下：的一般格式如下： f(sn+1)=g(f(

8、si),f(si+1),f(sn),cj,cj+1,cm) (6.2) 其中其中, n,i,j,m均为正整数。均为正整数。 sn+1是一个递归是一个递归“大问题大问题”, si,si+1,sn为递归为递归“小问题小问题”, cj,cj+1,cm是可以用非递归方法直接解决的问题是可以用非递归方法直接解决的问题 g是一个非递归函数是一个非递归函数,可以直接求值。可以直接求值。递归思路递归思路 实际上实际上, 递归思路是把一个递归思路是把一个不能或不好直接求解不能或不好直接求解的的“大问题大问题”转化成一个或几个转化成一个或几个“小问题小问题”来解决来解决,再把这些再把这些“小问题小问题”进一步进一

9、步分解分解成更小的成更小的“小问题小问题”来解决来解决,如此分解如此分解,直至每个直至每个“小问题小问题”都可以直接解都可以直接解决决(此时此时分解到递归出口分解到递归出口)。 但递归分解不是随意的分解但递归分解不是随意的分解,递归分解递归分解要保证要保证“大大问题问题”与与“小问题小问题”相似相似,即求解过程与环境都相似。即求解过程与环境都相似。并且有一个并且有一个分解的终点分解的终点。从而使问题可解。从而使问题可解。 fun(5) d1:fun(4) d2:fun(3) d3:fun(2) d4:fun(1) 返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=

10、120 求解求解5!的过程如下：的过程如下：斐波那契数列的递归调用树斐波那契数列的递归调用树递归的执行过程由递归的执行过程由分解过程分解过程和和求值过程求值过程两部分构成。两部分构成。 分解过程分解过程是是“量变量变”过程过程,即原来的即原来的“大问题大问题”在慢慢在慢慢变小变小,但尚未解决；遇到递归出口后但尚未解决；遇到递归出口后,便发生了便发生了“质质变变”,即原递归问题便转化成直接问题。即原递归问题便转化成直接问题。6.2 6.2 递归算法的设计递归算法的设计 递归的求解的过程均有这样的特征：先递归的求解的过程均有这样的特征：先将整个问题将整个问题划分为若干个子问题划分为若干个子问题,通

11、过分别求解子问题通过分别求解子问题,最后获得最后获得整个问题的解。而这些整个问题的解。而这些子问题具有与原问题相同的求子问题具有与原问题相同的求解方法解方法,于是可以再将它们划分成若干个子问题于是可以再将它们划分成若干个子问题,分别分别求解求解,如此反复进行如此反复进行,直到不能再划分成子问题直到不能再划分成子问题,或已经或已经可以求解为止。这种自上而下将问题分解、求解可以求解为止。这种自上而下将问题分解、求解,再自再自上而下引用、合并上而下引用、合并,求出最后解答的过程称为递归求解求出最后解答的过程称为递归求解过程。这是一种过程。这是一种分而治之分而治之的算法设计方法。的算法设计方法。 递归

12、算法设计先要给出递归算法设计先要给出递归模型递归模型,再转换成对应的再转换成对应的C/C+语言函数。语言函数。 递归设计的步骤如下：递归设计的步骤如下： (1)对原问题对原问题f(s)进行分析进行分析,假设出合理的假设出合理的“较小问较小问题题”f(s)(与数学归纳法中假设与数学归纳法中假设n=k-1时等式成立相似时等式成立相似)； (2)假设假设f(s)是可解的是可解的,在此基础上确定在此基础上确定f(s)的解的解,即给出即给出f(s)与与f(s)之间的关系之间的关系(与数学归纳法中求证与数学归纳法中求证n=k时等式成时等式成立的过程相似立的过程相似)； (3)确定一个特定情况确定一个特定情

13、况(如如f(1)或或f(0)的解的解,由此作为由此作为递递归出口归出口(与数学归纳法中求证与数学归纳法中求证n=1时等式成立相似时等式成立相似)。 例如例如,采用递归算法求实数数组采用递归算法求实数数组A0.n-1中的最小值。中的最小值。 假设假设f(A,i)函数求数组元素函数求数组元素A0Ai中的最小值。中的最小值。 当当i=0时时,有有f(A,i)=A0； 假设假设f(A,i-1)已求出已求出,则则f(A,i)=MIN(f(A,i-1),Ai),其中其中MIN()为求两个值较小值函数。因此得到如下递归模型：为求两个值较小值函数。因此得到如下递归模型： A0 当当i=0时时 f(A,i)=

14、MIN(f(A,i-1),Ai) 其他情况其他情况由此得到如下递归求解算法：由此得到如下递归求解算法： float f(float A,int i) float m; if (i=0) return A0; else m=f(A,i-1); if (mAi) return Ai; else return m; 6.3 6.3 递归算法到非递归算法的转换递归算法到非递归算法的转换 递归算法有两个基本特性：一是递归算法是一种分递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方而治之的、把复杂问题分解为简单问题的求解问题方法法,对求解某些复杂问题对求解某些复杂

15、问题,递归算法分析问题的方法是十递归算法分析问题的方法是十分分有效有效的；二是递归算法的的；二是递归算法的时间时间/空间效率通常比较差空间效率通常比较差。 因此因此,对求解某些问题时对求解某些问题时,我们希望我们希望用递归算法分析用递归算法分析问题问题,用非递归算法具体求解问题用非递归算法具体求解问题。这就需要把递归算。这就需要把递归算法转换为非递归算法。法转换为非递归算法。把递归算法转化为非递归算法有如下三种基本方法：把递归算法转化为非递归算法有如下三种基本方法： (1)通过分析，跳过通过分析，跳过分解过程分解过程，直接用，直接用循环结构循环结构的算的算法实现法实现求值过程求值过程。 (2)

16、自己用自己用栈栈模拟系统的运行时栈模拟系统的运行时栈,通过分析只保存必通过分析只保存必须保存的信息须保存的信息,从而用非递归算法替代递归算法。从而用非递归算法替代递归算法。 (3)利用利用栈栈保存参数保存参数,由于栈的后进先出特性吻合递归由于栈的后进先出特性吻合递归算法的执行过程算法的执行过程,因而可以用非递归算法替代递归算法。因而可以用非递归算法替代递归算法。6.3.1 6.3.1 利用循环跳过分解过程从而消除递归利用循环跳过分解过程从而消除递归 采用循环结构消除递归。求解采用循环结构消除递归。求解Fibonacci数列的算数列的算法如下：法如下： int Fib(int n) int i,

17、f1,f2,f3; if (n=1 | n=2) return(n); f1=1;f2=2; for (i=3;i-1) /*栈不空时循环栈不空时循环*/ if (Sttop.tag=1) /*未计算出栈顶元素的未计算出栈顶元素的vf值值*/ if (Sttop.vn=0)/*(1)式式*/ Sttop.vf=1; Sttop.tag=0; else/*(2)式式*/ top+; Sttop.vn=Sttop-1.vn-1; Sttop.tag=1; else if (Sttop.tag=0) /*已计算出已计算出vf值值*/ Sttop-1.vf=Sttop-1.vn*Sttop.vf; /*(2)式式*/ Sttop-1.tag=0; top-; /*栈中只有一个已求