小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. C/C++
  5. 正文

C++递归用法

2015年4月8日 2177点热度 0人点赞 0条评论

很多初学者往往对递归迷惑不解,也在这上面花了不少的时间。其实教材上的例子很经典,只是它说的有一些唠叨了。初学者会看的头大的。编程是解决问题的,而现实中很多的问题都是比较简单的,没有象汉诺塔那么复杂。我们也不必追究递归到底是怎样实现的,我们只是要会用递归,会用递归来为我们解决一些问题,这就行了。
首先来看一个例子:

有一个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==1) return 1; /*停止条件*/
else
return (n+f(n-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)); /*实现递归*/
}
怎么样,很简单吧。 会用循环求解吗?

递归在实际的编程中并不常用,但是在某些情况下,它是非常强有力而漂亮的工具。掌握它的原理时会十分有用的。

转自:

 

其它参考:

1、  http://www.nbrkb.net/lwt/jsjsj/sjjg&sf/c++dgyf.htm

2、  http://www.e-van.net/c-prog-hannuo.html

3、  http://www.cppblog.com/haosola/archive/2009/11/17/101163.aspx

4、  http://www.cnblogs.com/eslizn/archive/2011/05/29/2062043.html

5、  http://edu.3gmgc.com/tuwenjiaocheng/C__/diwuzhang_hanshuyuyuchuli/455.html

6、  http://www.asp119.com/program/ccc/2010-09-25/570.html

7、  http://comapp.ecjtu.jx.cn/view.php?id=45

8、  http://webservices.ctocio.com.cn/35/11398035.shtml

9、  http://www.gzu521.com/campus/article/it/200701/139273.htm

转自:http://bbs.ikaka.com/showtopic-664019.aspx

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2015年4月8日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
大二上学期期末考试复习计划 小花豆生活第∞天:写在青岛世园会闭幕之时 2010 S.V Beijing Travel 18:Home Ticket 莱芜一中2012届高一(53级)分班表 新版xero官方网站即将启用 新青年报[New Youth]第八期(高考录取特刊)即将发布
标签聚合
学习 Java 算法 python学习 leetcode 高中 linux 鸟哥的linux私房菜 生活 Python
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号