计算机中的递归思想4

发布网友发布时间：2024-03-04 06:47

共4个回答

热心网友时间：2024-04-09 07:22

简单谈谈C++ 递归的思想实现以及和循环的关系　文/　出处：it.com.cn 　　很多初学者往往对递归迷惑不解，也在这上面花了不少的时间。其实教材上的例子很经典，只是它说的有一些唠叨了。初学者会看的头大的。编程是解决问题的，而现实中很多的问题都是比较简单的，没有象汉诺塔那么复杂。我们也不必追究递归到底是怎样实现的，我们只是要会用递归，会用递归来为我们解决一些问题，这就行了。

　　首先来看一个例子：

　　有一个Febonacci序列：

　　1,1,2,3,5,8,13,,21,34........

　　它的问题是：求这个序列中的第N个数。

　　由于它的函数原形是：f(n)=f(n-1)+f(n-2)

　　这用递归很容易就可以写出代码来，一点都不费事：

　　int Febc(int n) {

　　if(n<3) return (1);

　　else

　　return (Febc(n-1)+Febc(n-2));

　　}

　　噢~~~~~也许你会说递归真是太简单了，简直就是一个数学模型嘛，呵呵。

　　其实，递归函数的工作过程就是自己调用自己。有一些问题用递归就很容易解决，简单的你自己都会吃惊。

　　我们做事情，一般都是从头开始的，而递归却是从末尾开始的。比如上面的函数吧，当n>3时，它显然只能求助于n-1,n-2。而(n-1)>2,(n-2)>2时，它们就求助于：(n-1)-1,(n-1)-2;(n-2)-1,(n-2)-2;然后··············直到（n-k)<3,(n-k-1)<3时，函数Febc终于有了返回值1 了，它再从头开始计算，然后一直算到n 为止。

　　通过上面的例子，我们知道递归一定要有一个停止的条件，否则递归就不知道停止了。在上面的例子中， if(n<3) return (1); 就是停止的条件。

　　然而，使用递归的代价是十分巨大的：它会消耗大量的内存！！递归循环时它用的是堆栈，而堆栈的资源是十分有限的。上面的例子你只能用一个很小的n值。如果n=20，即Febc(20)的话，它将调用Febc(n)函数10000多次！！！而上面一个例子用循环也是十分容易写的：

　　/*using turboc2*/
　　int febc(int);
　　main()
　　{
　　int n;
　　scanf("%d",&n);
　　febc(n);
　　}

　　int febc(int n)
　　{
　　int a[3],i;
　　a[0]=a[1]=a[2]=1;
　　for(i=3;i<=n;i++)
　　a[i%3]=a[(i+1)%3]+a[(i+2)%3]; /*实现 Febc(i)=Febc(i-1)+Febc(i-2)*/
　　printf("\n%d\n",a[n%3]);
　　}

　　有兴趣者不妨输入一个较大的n值，然后比较比较这二个函数计算的速度。当然，如果你使用的n太大的话，递归可能发生错误。如果死机了可别骂我哦~~~ 我已经提醒过你了：）

　　现在我们再来看看一个求从1 加到100的循环：

　　/*turboc2*/

　　main()

　　{ int i,n;

　　for(i=1;i<101;i++)

　　n+=i; }

　　这很简单没什么可说的。但是，你能不能写出相应的递归函数呢？

热心网友时间：2024-04-09 07:22

递归就是自己调用自己

热心网友时间：2024-04-09 07:25

递归就是一个函数自己call自己。void Func(){ Func();}递归很简单，一般复杂的遍历会使用递归。但是，递归成本很高，有堆栈溢出的风险，一般在高安全性场合，禁止使用递归方式开发。还是看使用场景了。

热心网友时间：2024-04-09 07:19

我用VB写个 n!给你看n!=1*2*3*...n也可以说是 n!=n*(n-1)!function yt(byval n as integer) as long dim rtn as longif n=1 then rtn=1elsertn = n* yt(n-1)endif yt=rtnend function