第一种写法
def fib(n:Int):Int = { def loop(i:Int):Int = { i match { case 1 => 0 case 2 => 1 case _ => loop(i - 1) + loop(i - 2) } } loop(n) }
相信有一定的编程能力的人,写这么一个递归函数应该不难,也是与人的思维最相近的,但是很明显,两层递归对栈的消耗完全是指数级的,写完这个,后续一定会考虑如何优化. 尾递归优化是针对递归非常常用的优化方式,那么问题来了,如何对上述的代码进行可以尾递归的改造. 通常的做法也容易想,就是递归方法中存放中间结果.那么下一个版本的代码如下
第二种写法
def fib2(n:Int):Int = { @annotation.tailrec def loop(n:Int,pre:Int,current:Int):Int={ if(n == 1){ pre } else { loop(n-1,current,current+pre) } } loop(n,0,1) }
数组从0,1 开始,然后一共走N位,最后走到1的时候,就是pre的值.
第三种写法
def fib3(n:Int):Int = { def loop(first:Int,second:Int):Stream[Int] = first #:: loop(second,first+second) loop(0,1).take(n).last }
这个是用了scala里非常典型的stream ,这样的话,可以说既与一般人的思维方式相匹配,又避免了栈依赖过多的问题.
总结
总体的感觉还是不到位,后续如果思维更加清晰了,再补充一下吧.
相关推荐
Fibonacci数列斐波那契数列PPT学习教案.pptx
Fibonacci数列,用c++编写的,非递归的函数调用求Fibonacci数列的第n项
本文档提供了两种计算斐波那契的C++代码函数,供网友使用,。主要讲cpp添加到新建项目中运行
【问题描述】编写函数f,功能是用递归的方法求斐波那契数列的第n项,函数原型为 int f(int n),在主函数中输入一个正整数n,调用函数f求出斐波那契数列的第n项,并在主函数中输出。 斐波那契数列:1,1,2,3,5,8,13,...
在数学上它以递归的方式进行定义,指这样的一个数列:0、1、1、2、3、5、8、13、21、34、55、89、144……,即前两个数为分别为0和1,从第3项开始,每项的值都等于其前两项之和。斐波那契数列Fib(n)用公式表示为: ...
本代码使用C++语言书写,编译环境VS2013。...斐波那契数列(Fibonacci Sequence)又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、…… 本代码是练习作品,如有错误或修改,请指正,感谢感谢。
利用递归数列求解著名的Fibonacci数列的各项,用户可自定义输入要求的第n项,输入后即可求出从0到n每一项Fibonacci的值。
程序分析:斐波那契数列(Fibonacci sequence),又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、…… 在数学上,费波那契数列是以递归的方法来定义: F0 = 0 (n=0) F1 = 1 (n=1) Fn ...
C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++...
利用数组计算斐波那契数列
C语言程序设计-用函数求fibonacci数列前n项的和;说明:fibonacci数列为数列的第一项值为1,第二项值也为1,从第三项开始,每一项均为其前面相邻两项的和;例如:当n=28时,运行结果:832039.c
编写一个Java程序,用于输出Fibonacci数列的前20项。
使用Logisim搭建一个根据输入序号x计算对应序号斐波那契数fib[x]的电路(输入序号0对应输出数0,输入序号1对应输出数1,输入序号2对应输出数1,以此类推)并提交。
android Handler子线程计算斐波那契数列
递归方法 def fibonacci(n): if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) n = int(input("请输入要计算的斐波那契数列的项数:")) print("斐波那契数列的第", n, "项为:", fibonacci(n)) 2...
从一个十分简明的递推关系出发,竟引出了一个充满奇趣的数列.它与植物生长等自然现象,以及几何图形、黄金分割、杨辉三角、矩阵运算等数学知识有着非常微妙的联系,并且在优选法、计算机科学等领域中得到广泛应用。...
【C++】斐波那契数列应用的一个实例。这是关于斐波那契数列的一个例子,用C++语言实现
一个特殊数列与Fibonacci数列的关系,王雅茹,朱福惠,本文在Fibonacci数列的基础上定义了前四项分别是1,4,7,9,并且满足第n项是第n-1 项与第n-3项和第n-4项之和的数列,并通过改变其部分项得到�
# 题目:斐波那契数列。 # 程序分析:斐波那契数列(Fibonacci sequence),从1,1开始,后面每一项等于前面两项之和。图方便就递归实现,图性能就用循环。
C++ 斐波那契数列分数式 #include using namespace std; int main() { float j,k,s; int a,i; char t; j=2.0;k=1.0; for(i=1;i;i++) { s=s+j/k; t=j;j=k;k=t; j=j+k; } cout; cin>>a; return 0; }