浅谈递归机制和非递归转换

时间:2010-04-30 11:52:02  来源:第二电脑网  作者:第二电脑网

  第二电脑网导读:指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质的子问题的求解,而小问题的求解过程可以很容易的求出,这些子问题的解就构成里原问题的解了。二、递归的几个特点1.递归式,就是如何将原问题划分成子问题。2.递归出口,递归终止的条件,即最小子问题的求解,可以允许多个出口。3.界函数,问题规模变化的函数,它保证递归的规模向出口条...
  正文:

写来玩玩,希望大家都给点意见.


一、什么是递归

很多数据结构的定义都是根据递归性质来进行定义的,是因为这些结构固有的性质。
递归是指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质
的子问题的求解,而小问题的求解过程可以很容易的求出,这些子问题的解就构成里原
问题的解了。

二、递归的几个特点
1.递归式,就是如何将原问题划分成子问题。
2.递归出口,递归终止的条件,即最小子问题的求解,可以允许多个出口。
3.界函数,问题规模变化的函数,它保证递归的规模向出口条件靠拢

三、递归的运做机制
很明显,很多问题本身固有的性质就决定此类问题是递归定义,所以递归程序很直接
算法程序结构清晰、思路明了。但是递归的执行过程却很让人费解,这也是让很多人
难理解递归的原因之一。由于递归调用是对函数自身的调用,在一次调用没有结束之前
又开始了另外一次调用,按照作用域的规定,函数在执行终止之前是不能收回所占用的
空间,必须保存下来,这也就意味着每一次的调用都要把分配的相应空间保存起来。为
了更好管理这些空间,系统内部设置一个栈,用于存放每次函数调用与返回所需的各种
数据,其中主要包括函数的调用结束的返回地址,返回值,参数和局部变量等。
其过程大致如下:
1.计算当前函数的实参的值
2.分配空间,并将首地址压栈,保护现场
3.转到函数体,执行各语句,此前部分会重复发生(递归调用)
4.直到出口,从栈顶取出相应数据,包括,返回地址,返回值等等,收回空间,恢复现场,转到上一
层的调用位置继续执行本次调用未完成的语句。

四、引入非递归
从用户使用角度来说,递归真的很简便,对程序宏观上容易理解。递归程序的时间复杂度虽然可以根据
T(n)=T(n-1)*f(n)递归求出,其中f(n)是递归式的执行时间复杂度,一般来说,时间复杂度和对应的非

递归差不多,但是递归的效率是相当低的它主要发费在反复的进栈出栈,各种中断等机制上(具体的可

以参考操作系统)更有甚者,在递归求解过程中,某些解会重复的求好几次,这是不能容忍的,这些也

是引入非递归机制的原因之一。

五、递归转非递归的两种方法
1.一般根据是否需要回朔可以把递归分成简单递归和复杂递归,简单递归一般就是根据递归式来找出递

推公式(这也就引申出分治思想和动态规划)。而复杂递归一般就是模拟系统处理递归的机制,使用栈

或队列等数据结构保存回朔点来求解。

六、几个简单的例子
1.求解阶乘
阶乘的定义就是 n!=n*(n-1)! 0!=1 1!=1
根据定义我们很容易就想到递归方法,做法如下
int Fact(int n)
{
  if(n==0) return 1; //递归出口
  return n*Fact(n-1) //n*Fact(n-1)就是递归式,其中n-1就是界函数
}
2.再看Fibonacci的例子
定义:某项的值等于前两项的和,其中第一和第二项为1。
根据定义我们很容易写出程序,这里就不写出来了,当我们用笔划几下的时候我们是否会发现有很多解

是重复求出的。举个例子要求F(5)
F(5)=F(4)+F(3);
F(4)=F(3)+F(2);
F(3)=F(2)+F(1);
其中F(3)求解2次。这显然就是时间的浪费。下面我们用递推技术来转化成非递归
从例子可以发现我们可以倒过来求解,即从底到顶把F(n)之前要计算的东西保存下来。
程序就是:

int Fibona(int n)
{
  int p1=1,p2=1;
  //int a[100]={0};
  //a[1]=1,a[2]=1;
  for(int i=3;i<=n;i++)       //从三开始就可以了,后面的return包括1,2两种情况
  {
     int r=p1;          //递推,可以使用数组全部保存
     p1=p2;
     p2+=r;
     //a[i]=a[i-1]+a[i-2]
  }
  return p2;
  //return a[n];
}

3.带回朔的复杂递归:具体例子参照二叉树的遍历程序。
http://bbs.bccn.net/thread-137061-1-1.html

举个简单点的:求解按照中点优先的顺序遍历线形表
按照定义,当然是想到先输出求解的线形表中点值,再输出左部分,然后右部分。
部分代码如下:

void Mid_Order(int a[],int left,int right)
{
  int mid;
  if(left<right)
  {
    mid=(left+rigth)/2;
    printf("%d ",a[mid]);      //输出中点
    Mid_Order(a,left,mid-1);     //递归调用左部
    Mid_Order(a,mid+1,right);    //递归调用右部
  }
}

显然,在非递归中必须在打印中点之后即将要要访问左部时,要把右部的信息保存起来,结合访问顺序

的特点,知道这里要使用栈。具体做法在这就不实现了。^_^


浅谈递归机制和非递归转换》由第二电脑网原创提供,转载请注明:http://www.002pc.com/master/College/Language/VC/2010-04-30/13814.html


关键字:

关于《浅谈递归机制和非递归转换》文章的评论

站内搜索: 高级搜索

热门搜索: Windows style 系统 tr IP QQ CPU 安装 function 注册 if td