很多初学者往往对递归迷惑不解,也在这上面花了不少的时间。其实教材上的例子很经典,只是它说的有一些唠叨了。初学者会看的头大的。编程是解决问题的,而现实中很多的问题都是比较简单的,没有象汉诺塔那么复杂。我们也不必追究递归到底是怎样实现的,我们只是要会用递归,会用递归来为我们解决一些问题,这就行了。
首先来看一个例子:
有一个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; }
这很简单没什么可说的。 但是,你能不能写出相应的递归函数呢?
下面就是递归(请注意了,这种做法不推荐!! 我只是为了说明问题才这么写的。)
/*using Turboc2*/
int a=0;
int account(int);
main()
{
account(100);
printf("%d",a);
}
int account(int i)
{
if(i==0) return 0; /*停止条件*/
else
a+=account(i-1)+1; /*实现递归*/
}
在C/C++的问题中,我曾经回答过这样的一个问题:
若一头小母牛,从出生起第四个年头开始每年生一头母牛,按此规律,第n年时有多少头母牛? 请问如何用递归涵数求此问题?
先写出函数表达式:f(n)=f(n-1)+f(n-3)
为什么f(n)=f(n-1)+f(n-3)呢,请看:
f(n)-f(n-1)=f(n-3)
因为第n年要比n-1年多的牛,都是大于三岁的牛生的小牛,而f(n-3)正是那些在n年大于三岁的牛,然后它们在第n年生下相同数量的小牛。(请用BorlandC++3.1或其他C++编译器)
#include<iostream.h>
#include<conio.h>
int cattle(int,int);
void main()
{
int ct,n;
cout<<"Please input the original cattle number:"<<endl; /*输入起始牛的数量*/
cin>>ct;
cout<<"Input how many years it past:"<<endl;
cin>>n;
cout<<"You have "<<cattle(ct,n)<<" cattle now!"<<endl;
getch();
}
int cattle(int ct,int n)
{
if(n<4) return (ct); /*停止条件*/
else
return (cattle(ct,n-1)+cattle(ct,n-3)); /*实现递归*/
}
怎么样,很简单吧。 会用循环求解吗?
递归在实际的编程中并不常用,但是在某些情况下,它是非常强有力而漂亮的工具。掌握它的原理时会十分有用的。
分享到:
相关推荐
c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘...
归并分类 计算机算法 c/c++语言 递归和非递归
汉诺塔代码(c/c++递归) 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。上帝创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从...
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...
C++递归课件 简单的递归思想 递归思想入门
递归算法ppt C/C++ acm 蓝桥杯等竞赛的可以看下
递归很难理解吗? 看看这个整理的文件吧,相信会有收获的
这是一个用c++写的用来实现编译原理里面文法分析的递归下降分析法。
c++语言的简单程序示例,通过递归方法求数组。
在C++中利用递归思想实现反序数
递归算法在C/C++程序设计的描述与实现
在程序设计中,数据描述和算法表达也常用递归,通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的...
C/C++:实现迷宫问题的最优解的非递归算法.rar(含完整注释)
c++递归函数的使用,介绍了使用递归实现数组遍历和阶乘函数的函数
这里是本蒟蒻整理/写的递归递推经典题目 上传供大家学习使用 包含:过河卒、过河卒升级版、汉诺塔、级数求和、勒让德多项式、流感传染、判断回文、判断元素是否存在、平方根级数、平面分割升级版、全排列递归版、...
二分法 解函数 c++语言 c语言 递归 数根
C++递归算法搜索遍历windows磁盘文件--》应用程序 Email:982646379@qq.com
c++递归反转字符串代码 大家可以参考看看 欢迎分享
可实现: 输入相应元素,用先序创建二叉树(无元素处用“#”) 递归先序遍历二叉树: 递归中序遍历二叉树: 递归后序遍历二叉树: 非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: ...
实现迷宫问题的最优解的递归算法