递归算法求斐波那契数列的流程图

1. 前言

本节内容是递归算法系列之一:斐波那契数列递归求解,主要介绍了斐波那契数列的定义,然后用递归的实现思想分析了一下斐波那契数列,最后给出了基于 Java 代码应用递归思想实现斐波那契数列的代码实现及简单讲解。

2. 什么是斐波那契数列?

斐波那契数列(Fibonacci sequence),也称之为黄金分割数列,由意大利数学家列昂纳多・斐波那契(Leonardo Fibonacci)提出。斐波那契数列指的是这样的一个数列:1、1、2、3、5、8、13、21、34、……,这个数列从第 3 项开始,每一项都等于前面两项之和。在数学上,斐波那契数列可以被递推的方法定义如下:

F(1)=1,F(2)=1, F(n)=F(n – 1)+F(n – 2)(n ≥ 3,n ∈ N*)

斐波那契数列是数学上面一个经典的例子,并且在日常生活中有很多应用,他还与黄金分割有着密不可分的联系,而且当 n 趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割值 0.618。

3. 用递归方法求解斐波那契数列

在这一节中,我们就需要利用递归的思想去求解斐波那契数列,当给出一个斐波那契中第几项的数字,然后求解出对应的斐波那契数值。在之前,我们已经定义了递归算法的相关概念,并且明确了需要应用递归时候的三要素:

  1. 递归终止条件;
  2. 递归终止时候的处理方法;
  3. 递归中重复的逻辑提取,缩小问题规模。

接下来,我们将利用递归的知识来解决斐波那契数列问题,明确在斐波那契数列求解问题中的递归三要素分别是什么。

斐波那契数列的递归终止条件 显然易见,通过观察斐波那契数列的定义,我们很容易发现当 n=1 或者 n=2 时,是斐波那契数列的递归终止条件,这个时候可以给出斐波那契数列的具体值。

斐波那契数列递归终止时候的处理方法 同样的,基于斐波那契数列的递推定义,当斐波那契数列达到终止条件 n=1 或者 n=2 时,我们也很容易发现对应 F(1)=1,F(2)=1,这就是斐波那契数列在递归终止时对应的取值。

斐波那契数列的递归重复逻辑提取 按照斐波那契数列的数学定义,F(n)=F(n – 1)+F(n – 2)(n ≥ 3,n ∈ N*),即当 n ≥ 3 时,斐波那契数列中这一项的值等于前面两项的值之和,这样便可以将求解一个比较大的斐波那契数列转化为求解较小数值的斐波那契数列值,这里面有重复逻辑可以递归复用。

例如,当我们求解斐波那契数列中的 F(5) 时,按照定义,我们有:

F(5) = F(4) + F(3) // 递归分解 = ( F(3) + F(2) ) + ( F(2)+F(1) ) // 递归求解 ​ = [ ( F(2)+F(1) ) + 1 ] + ( 1+1 ) // 递归求解,遇到终止条件就求解 ​ = [(1+1) +1 ]+(1+1) // 归并 ​ = 3 + 2 // 归并 ​ = 5 // 归并

4. 基于 Java 代码示例及实现讲解

在说明斐波那契数列的递归描述之后,我们看看如何用 Java 代码来实现对斐波那契数列的计算。

public class Fibonacci { public static void main(String[] args){ System.out.println(fibonacci(1)); System.out.println(fibonacci(2)); System.out.println(fibonacci(3)); System.out.println(fibonacci(4)); System.out.println(fibonacci(5)); } //斐波那契数列数列的计算 private static int fibonacci(int n){ //如果是终止条件,按照要求返回终止条件对应结果 if( n==1 || n==2 ){ return 1; }else { //非终止条件,按照要求把大的问题拆分成小问题,调用自身函数递归处理 return fibonacci(n-1)+fibonacci(n-2); } }}

运行结果如下:

11235

代码中的第 4 行至第 8 行分别调用斐波那契数列计算函数,计算出斐波那契数列中对应 n=1,2,3,4,5 时斐波那契数列的取值,进行结果比较,判断斐波那契数列程序实现是否正确。代码中的第 12 行至第 20 行是斐波那契数列应用递归方法进行斐波那契数列的计算,按照递归的三要素进行计算处理。

5. 小结

本节主要介绍了用递归思想求解斐波那契数列,在学完本节课程之后,我们了解到了什么是斐波那契数列,并且将递归算法在斐波那契数列中进行了实际应用,需要掌握斐波那契数列的递归求解方法,并自己可以实现相关的代码实现,并清楚里面的每一步逻辑。

本网页内容旨在传播知识,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:dandanxi6@qq.com

(0)
上一篇 2023-12-29 11:42
下一篇 2023-12-29 13:08

相关推荐

  • 失业保障金如何申领,失业保险金怎么申领流程

    线上线下均可办理 符合条件者可享受多项待遇 失业保险金这样申领   失业保险是我国社会保障制度的重要组成部分,是单位和个人履行缴纳失业保险费义务后,劳动者失业时享受的一项保障生活的…

    2023-07-02
  • 对数值求和总是0怎么回事(对数运算必备五个技巧)

    Hello,大家好,相信大家在工作中一定都遇到过这样的情况,就是对数值进行求和,结果居然是0,如下图,百思不得其解这到底是为什么,今天就跟大家介绍下为什么有时候我们对数值求和它的结…

    2023-04-27
  • 商家入驻美团需要多少费用

    大家好,我是非远,今天我们来讨论一下。商家入驻美团需要多少费用呢?以我作为一个商家的经验。你加盟美团是不需要什么费用的。他收取的费用都是后期的费用。大概就是按你所卖菜品的原价的21…

    职场百科 2023-02-05
  • java开发自我评价简历

    自我评价(案例一) 1.参与多个项目的开发,超过1年的项目开发经验。 2.较高的执行能力造就较高的学习能力、动手能力。 3.思维灵活变通。有较高的产品观念和创新思维。 4.吃苦耐劳…

    职场百科 2023-02-22
  • 大学生网上赚零花钱的方法(在校生如何赚零花钱呢)

    大学生的课余时间是非常多的,利用这些时间,我们可以去做点小兼职赚点零花钱,既可以补贴生活费,又可以获得不一样的生活体验。 现在大学生完全可以不用去大街上发传单,或者去咖啡店当服务员…

    2023-01-16
  • 市场调研的方法有哪些?各有什么优缺点

    老吴评析: 企业在洞察市场、洞悉客户、洞见趋势时,获取的全面、深入、客观的市场和消费者信息是前置的必须;除了企业内部工作流及与客户交互过程中沉淀下来的信息和数据之外,市场调研是一个…

    职场百科 2023-02-23
  • 广州市城市规划布局,广州市城市规划勘测设计院招聘

    在中国,一提到一线国际化大都市,就会说“北上广深”。广州,无论是从城市国际竞争力还是城市国际化发展水平等国际化进程中的方方面面都走在国内大都市前列。截至2018年,随着天河区落户1…

    2023-07-09
  • 如何设计生命力更长的ip形象(如何设计夸张的ip形象)

    随着90后、90后成为消费主力,IP市场的消费模式也在发生变化。用户的消费偏好正在从单一的“物质消费”向复合的“精神消费”转变。大量客户用实际行动证明,他们越来越愿意为自己喜欢的I…

    职场百科 2023-03-15
  • 初学者怎样考取瑜伽教练证

    瑜伽是21世纪新一代流行的健身美体运动之一,近几年随着健身意识的深入人心以及瑜伽的广泛传播,国内也掀起了学习瑜伽的热潮。 据不完全统计,目前北上广深等城市的瑜伽老师还有很大缺口,专…

    2023-04-26
  • 如何开一个外卖店

    开快递和开其他的公司是一样的流程:第一,准备好场地,车辆,设备(包括网络、安检、消防、监控设施)然后要确定你是做加盟的还是做自有品牌的,目前国内大多数自己想做个快递店的都是加盟的!…

    2023-07-26