兔子数列递归算法实现的一些补充

兔子数列递归算法实现的一些补充


本文整理了一些兔子数列更多递归算法的实现,如【缓存递归】,【尾递归】等。但是性能都受栈空间大小的限制,并不是最佳的实现算法。

兔子数列动态规划实现,请点此链接查看

package algorithm;

public class Fibonacci {

	public static int[] fibarr;

	public static void main(String[] args) {

		// 求兔子数列第45位
		int n = 45;
		fibarr = new int[n + 1];

		System.out.println("求出值 " + fib(n)); // 1134903170

		
		System.out.println("开始尾递归!!!");
		System.out.println("求出值 " + tailFib(45, 1, 1)); // 1134903170
		
		

		System.out.println("大数字检测性能!!!");
		// 尾递归性能还是会有上限  相较于递归 压栈操作减少了 
		// 但是还是有很多压栈操作
		System.out.println("求出值 " + tailFib(1000, 1, 1)); // 817770325994397771
	}

	// 采用数组缓存递归子结果集 降低重复运算
	// 数据的存储收到数组大小的限制 也可用其他缓存变量来实现
	public static int fib(int n) {

		if (n <= 2) {
			return 1;
		}

		// 取缓存
		if (fibarr[n] > 0) {
			return fibarr[n];
		}

		int res = fib(n - 1) + fib(n - 2);

		// 放缓存
		fibarr[n] = res;
		return res;
	}

	// 尾递归 即从最小值开始往大运算
	// 输入 递归的次数 和 起始值
	public static long tailFib(int n, long firstRes, long secodeRes) {

//		System.out.print(n + "---");
//		System.out.print(firstRes + "---");
//		System.out.print(secodeRes);
//		System.out.println();
		
		if (n == 2) {
			return secodeRes;
		}

		return tailFib(n - 1, secodeRes, firstRes + secodeRes);
	}

}

附本机执行结果如下:

求出值 1134903170
开始尾递归!!!
求出值 1134903170
大数字检测性能!!!
求出值 817770325994397771

热门文章

暂无图片
编程学习 ·

react-native 使用react-native-image-crop-picker上传图片、视频到服务端

博主主要卡在了上传数据这一步情景是这样的:每一次只允许选择一张图片,每次从相册中选择一图片点击右上角确定后,立即发送请求,上传该图片,并且下次再点击时,重复这个动作。(1)点击下图的上传资料(2)点击红框内的按钮(3)选择图片(4)选择完毕的同时,上传图片到服…
暂无图片
编程学习 ·

读取csv文件,逐行写入txt

import csv #加载csv包便于读取csv文件x, y = [], [] csv_file = open(G:/竞赛/datafountain/O2O商铺食品安全相关评论发现/rnn_cnn/data/train.csv,encoding=utf-8) #打开csv文件 next(csv_file) csv_reader_lines = csv.reader(csv_file) #逐行读取csv文件 for one_l…
暂无图片
编程学习 ·

Unity的学习(二):打砖块

一、新建项目创建成功后,进入了如下界面。二、场景的设计 在Hierarchy中鼠标右键创建Plane(地面)游戏物体,将其Transform组件重置,并将游戏物体重命名为Ground,如下图所示。调整地面的大小。在Assets下创建文件夹Materials,并在其中创建Ground的Material(材质)并在Gro…
暂无图片
编程学习 ·

C++排雷:16. #pragma warning的几种用法

#pragma warning只对当前文件有效(对于.h,对包含它的cpp也是有效的),而不是对整个工程的所有文件有效。当该文件编译结束,设置也就失去作用。 #pragma warning(push)是保存当前的编译器警告状态;#pragma warning(push, n) 存储当前报警设置,并设置报警级别为n。n为从1到…
暂无图片
编程学习 ·

RabbitMQ 教程

RabbitMQ 教程 文章目录RabbitMQ 教程消息中间件安装及管理windows安装:RabbitMQLinux安装Mac安装基本概念主要概念Exchange的类型RabbitMQ的工作模式及代码示例简单模式 Simple2.工作模式 work (资源竞争消费)3.发布订阅 publish/subscribe (广播)4.路由 routing5.主题订阅…
暂无图片
编程学习 ·

spring+mybatis日志

spring4默认日志是log4j, spring5默认日志是JUL spring4下使用JCL时,如果有log4j的jar,用的具体实现类是log4j,否则用的具体实现类是JUL spring4下使用JCL时,用的具体实现类是JUL1、spring4下日志加载顺序//循环for(int i=0; i<classesToDiscover.length && resu…
暂无图片
编程学习 ·

iOS开发之多线程(2)—— Thread

目录版本简介方法属性示例 版本 Xcode 11.5 Swift 5.2.2 简介 一个Thread即为一个线程. 方法属性 OC中的属性方法(Swift方法名类似): #pragma mark - 属性 // 可以使用返回的字典来保存线程的特定数据. (这只是一个普通的字典, 用来保存所有开发者感兴趣的数据.) @property (r…
暂无图片
编程学习 ·

MySql简单入门_第四篇(2)_存储

5、存储过程:为以后的使用而保存的一条或多条MySql语句的集合存储过程(Stored Procedure)是一种在数据库中存储复杂程序,以便外部程序调用的一种数据库对象。存储过程是为了完成特定功能的SQL语句集,经编译创建并保存在数据库中,用户可通过指定存储过程的名字并给定参数(…
暂无图片
编程学习 ·

2020/7/1 方程根的存在性及个数/证明函数不等式

复习内容科目 内容 补充 时间数学 第九次课(83;148-151) 方程根的存在性及个数、证明函数不等式数学 题型三 方程的根的存在性及个数 1.存在性 方法1:零点定理; 方法2:罗尔定理。 2.根的个数 方法1:单调性 方法2:罗尔定理推论 推论:若在区间III上的f(n)(x)≠0f^{(n)}(…
暂无图片
编程学习 ·

笔记:R输入文件数据处理txt, csv,画饼图

R输入文件数据处理txt, csv, xlsx 数据处理 1)获取文件类型 parts = strsplit(infile, split=".", fixed = TRUE) ftype = parts[[1]][length(parts[[1]])]2)根据文件类型选择输入方式 if (ftype == "csv"){loandata<<-data.frame(read.csv(infile…
暂无图片
编程学习 ·

软件测试的基本流程

软件测试的基本流程 1. 测试需求分析阶段阅读需求 理解需求 主要就是对业务的学习 分析需求点 参与需求评审会议2. 测试计划阶段主要任务就是编写测试计划 参考软件需求规格说明书 项目总体计划,内容包括测试范围(来自需求文档),进度安排,人力物力的分配,整体测试策略的制…
暂无图片
编程学习 ·

faster-rcnn流程(mmdetection)

参考:http://chr10003566.github.io/2019/12/03/mmdetection(2)/ part1 测试mmdetection(通过读取一张图片,显示效果) demo.py from mmdet.apis import init_detector, inference_detector, show_result_pyplot import mmcvconfig_file = /home/ming/work/mmdetection/conf…
暂无图片
编程学习 ·

代码优化

也许有人会感觉CR没有什么卵用,只要我代码实现了功能,我完成了开发任务,我就OK了,为啥还要CR??但是CR真的是有必要的,你不仅可以发现自己代码中的不足之处,待优化点,简洁明了的代码易读别人接手也会很快。1. 比如在vue项目中只有某一个组件用某一个特别长的常量对象,…
暂无图片
编程学习 ·

FFmpeg快速压缩,短视频秒播,视频流m3u8生成

FFMpeg快速压缩test.mp4是视频地址 libx264表示视频编码格式为H.264 crf 表示控制转码,18-28比较合理,18表示无损压缩,28表示有损的压缩,28压缩出来的视频会模糊 test_compressed.mp4表示压缩后的视频路径ffmpeg -i test.mp4 -vcodec libx264 -crf 22 -preset veryfast -c:…
暂无图片
编程学习 ·

2020.7.1总结

前端知识: API: 判断是否为空: $.common.isEmpty() modal框: $.common.alertError() 弹层组件:layer layer.open({ title:false, type:1, closeBth:true, shadeClose:true,//阴影区域关闭 area:[‘auto’,‘atuo’]//宽,高 }) 以下是一些参数截图:layer组件:web弹层组…
暂无图片
编程学习 ·

前端学习-javascript-(1)预览

组成 DOM—Document Object Model 文档对象模型—操作返回到文档(界面) doucument对象 ———————————————— BOM—Browser Object Model 浏览器对象模型—操作浏览器本身 window对象 ———————————————— ECMAScript 解释器 ———————————…