`
cq520
  • 浏览: 166445 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

关于尾递归的一些疑惑

阅读更多

      前两天发了一篇关于递归的博客,感谢一位博主提出了尾递归的概念,之前还没了解过尾递归,这两天稍微弄了一下尾递归,发现了尾递归的确实相对于传统的树形递归有着效率上的优势,不过通过比对之后我还是发现了一个问题,不知道哪位博主能帮帮忙?

       在上一篇博客中就已经说到递归调用时,系统会记录递归链,使用树形递归计算连整数的和时,数字过大就会溢出栈空间。所以通过前两天一位博主提出的尾递归的概念,我也进行了一些资料的搜索,百度百科上面关于尾递归有这样一个例子:

线性递归:

long Rescuvie(long n) {

return(n == 1) ? 1 : n * Rescuvie(n - 1);

}

尾递归:

long TailRescuvie(long n, long a) {

return(n == 1) ? a : TailRescuvie(n - 1, a * n);

}

long TailRescuvie(long n) {//封装用的

return(n == 0) ? 1 : TailRescuvie(n, 1);

}

n = 5

对于线性递归, 他的递归过程如下:

Rescuvie(5)

{5 * Rescuvie(4)}

{5 * {4 * Rescuvie(3)}}

{5 * {4 * {3 * Rescuvie(2)}}}

{5 * {4 * {3 * {2 * Rescuvie(1)}}}}

{5 * {4 * {3 * {2 * 1}}}}

{5 * {4 * {3 * 2}}}

{5 * {4 * 6}}

{5 * 24}

120

对于尾递归, 他的递归过程如下:

TailRescuvie(5)

TailRescuvie(5, 1)

TailRescuvie(4, 5)

TailRescuvie(3, 20)

TailRescuvie(2, 60)

TailRescuvie(1, 120)

120

       看下来之后大概也了解了尾递归的过程,不过把这段代码放到eclipse里面去运行,经过反复测试之后,发现它比之前所写的树形结构的递归更容易溢出栈空间,很明显,它记录的递归链比线性递归的还要长,但这是为什么呢?希望一些大牛们来指出。

       不过,通过尾递归的思想,我已经解决了之前所提到的用递归求解fibonacci数的效率问题,算法如下:

     /**

     * 尾递归求fibonacci

     */

    long Tailfibonacci(int n){

       if(n<=2){

           return 1;

       }

       return Tailfibonacci(n,1,1);

    }

    long Tailfibonacci(int n,int a,int b){

       int c=a+b;

       if(n<=3){

           return c;

       }

       a=b;

       b=c;

       return     Tailfibonacci(n-1,a,b);

    }

    这个算法求解fibonacci数的效率是线性的,感谢博主们的帮助。

2
5
分享到:
评论

相关推荐

    pandas-1.3.5-cp37-cp37m-macosx_10_9_x86_64.zip

    pandas whl安装包,对应各个python版本和系统(具体看资源名字),找准自己对应的下载即可! 下载后解压出来是已.whl为后缀的安装包,进入终端,直接pip install pandas-xxx.whl即可,非常方便。 再也不用担心pip联网下载网络超时,各种安装不成功的问题。

    基于java的大学生兼职信息系统答辩PPT.pptx

    基于java的大学生兼职信息系统答辩PPT.pptx

    基于java的乐校园二手书交易管理系统答辩PPT.pptx

    基于java的乐校园二手书交易管理系统答辩PPT.pptx

    tornado-6.4-cp38-abi3-musllinux_1_1_i686.whl

    tornado-6.4-cp38-abi3-musllinux_1_1_i686.whl

    Android Studio Ladybug(android-studio-2024.2.1.10-mac.zip.002)

    Android Studio Ladybug 2024.2.1(android-studio-2024.2.1.10-mac.dmg)适用于macOS Intel系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/89954174 part2: https://download.csdn.net/download/weixin_43800734/89954175

    基于ssm框架+mysql+jsp实现的监考安排与查询系统

    有学生和教师两种角色 登录和注册模块 考场信息模块 考试信息模块 点我收藏 功能 监考安排模块 考场类型模块 系统公告模块 个人中心模块: 1、修改个人信息,可以上传图片 2、我的收藏列表 账号管理模块 服务模块 eclipse或者idea 均可以运行 jdk1.8 apache-maven-3.6 mysql5.7及以上 tomcat 8.0及以上版本

    tornado-6.1b2-cp38-cp38-macosx_10_9_x86_64.whl

    tornado-6.1b2-cp38-cp38-macosx_10_9_x86_64.whl

    Android Studio Ladybug(android-studio-2024.2.1.10-mac.zip.001)

    Android Studio Ladybug 2024.2.1(android-studio-2024.2.1.10-mac.dmg)适用于macOS Intel系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/89954174 part2: https://download.csdn.net/download/weixin_43800734/89954175

    基于MATLAB车牌识别代码实现代码【含界面GUI】.zip

    matlab

    基于java的毕业生就业信息管理系统答辩PPT.pptx

    基于java的毕业生就业信息管理系统答辩PPT.pptx

    基于Web的毕业设计选题系统的设计与实现(springboot+vue+mysql+说明文档).zip

    随着高等教育的普及和毕业设计的日益重要,为了方便教师、学生和管理员进行毕业设计的选题和管理,我们开发了这款基于Web的毕业设计选题系统。 该系统主要包括教师管理、院系管理、学生管理等多个模块。在教师管理模块中,管理员可以新增、删除教师信息,并查看教师的详细资料,方便进行教师资源的分配和管理。院系管理模块则允许管理员对各个院系的信息进行管理和维护,确保信息的准确性和完整性。 学生管理模块是系统的核心之一,它提供了学生选题、任务书管理、开题报告管理、开题成绩管理等功能。学生可以在此模块中进行毕业设计的选题,并上传任务书和开题报告,管理员和教师则可以对学生的报告进行审阅和评分。 此外,系统还具备课题分类管理和课题信息管理功能,方便对毕业设计课题进行分类和归档,提高管理效率。在线留言功能则为学生、教师和管理员提供了一个交流互动的平台,可以就毕业设计相关问题进行讨论和解答。 整个系统设计简洁明了,操作便捷,大大提高了毕业设计的选题和管理效率,为高等教育的发展做出了积极贡献。

    机器学习(预测模型):2000年至2015年期间193个国家的预期寿命和相关健康因素的数据

    这个数据集来自世界卫生组织(WHO),包含了2000年至2015年期间193个国家的预期寿命和相关健康因素的数据。它提供了一个全面的视角,用于分析影响全球人口预期寿命的多种因素。数据集涵盖了从婴儿死亡率、GDP、BMI到免疫接种覆盖率等多个维度,为研究者提供了丰富的信息来探索和预测预期寿命。 该数据集的特点在于其跨国家的比较性,使得研究者能够识别出不同国家之间预期寿命的差异,并分析这些差异背后的原因。数据集包含22个特征列和2938行数据,涉及的变量被分为几个大类:免疫相关因素、死亡因素、经济因素和社会因素。这些数据不仅有助于了解全球健康趋势,还可以辅助制定公共卫生政策和社会福利计划。 数据集的处理包括对缺失值的处理、数据类型转换以及去重等步骤,以确保数据的准确性和可靠性。研究者可以使用这个数据集来探索如教育、健康习惯、生活方式等因素如何影响人们的寿命,以及不同国家的经济发展水平如何与预期寿命相关联。此外,数据集还可以用于预测模型的构建,通过回归分析等统计方法来预测预期寿命。 总的来说,这个数据集是研究全球健康和预期寿命变化的宝贵资源,它不仅提供了历史数据,还为未来的研究和政策制

    基于微信小程序的高校毕业论文管理系统小程序答辩PPT.pptx

    基于微信小程序的高校毕业论文管理系统小程序答辩PPT.pptx

    基于java的超市 Pos 收银管理系统答辩PPT.pptx

    基于java的超市 Pos 收银管理系统答辩PPT.pptx

    基于java的网上报名系统答辩PPT.pptx

    基于java的网上报名系统答辩PPT.pptx

    基于java的网上书城答辩PPT.pptx

    基于java的网上书城答辩PPT.pptx

    婚恋网站 SSM毕业设计 附带论文.zip

    婚恋网站 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B

    基于java的戒烟网站答辩PPT.pptx

    基于java的戒烟网站答辩PPT.pptx

Global site tag (gtag.js) - Google Analytics