Fibonacci函数有两种很经典的实现
一种是以while为基础的:
public long Fib_Loop(int n)
{
long b1 = 1, b2 = 1, temp, begin = 3;
for (; begin <= n; ++begin)
{
temp = b1;
b1 = b2;
b2 = temp + b2;
}
return b2;
}
一种是以递归为基础的:
public long Fib_Recur(int n)
{
if (n == 1 || n == 2) //line1
return 1; //line2
else
return Fib_Recur(n - 1) + Fib_Recur(n - 2); //line 3
}
很明显这种递归效率极低:
Fib(6) = Fib(5) + Fib(4);
= Fib(4) + Fib(3) + Fib(3) + Fib(2);
= Fib(3) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
= Fib(2) + Fib(1) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
= 8
Notice that the first call on line 3,Fib(N-1),actually computes Fib(N-2) at some point.This information is thrown away and recomputed by the second call on line3.The amount of information thrown away componds recursively and results in the huge running time.This is perhaps the finest example of the maxim "Don't compute anything more than once" and should not scare you away from using recursion.
--《Data Structures and Algorithm Analysis》
另外一种高效率的递归:
public long Fib_Tail(int n)
{
if (n == 1 || n == 2)
return 1;
else
return Tail(n, 1, 1, 3);
}
//Typical help function...
private long Tail(int n, long b1, long b2, int begin)
{
if (n == begin)
{
return b1 + b2;
}
else
return Tail(n, b2, b1 + b2, begin + 1);
}
使用尾递归,而且计算几乎完全发生在尾递归中。
再说到Scala中的尾递归。由于函数式编程提倡在函数体中不适用var,所以一般的while式的命令式代码(imperative code)是建议被替换的,也就是说你可能会先写出while形式的语句,然后对其进行一番考究,看其是否能转换为函数式的代码。同时,在Scala中,尾递归是会被编译器优化的(虽然编写尾递归是有许多的限制),使其能够达到一般while语句的执行效率。
def boom(x: Int): Int =
if (x == 0) throw new Exception("boom!")
else boom(x - 1) + 1
//This function is not tail recursive, because it performs an increment operation
//after the recursive call.
def bang(x: Int): Int =
if (x == 0) throw new Exception("bang!")
else bang(x 1)
A tail-recursive function will not build a new stack frame for each call; all calls will execute in a single frame.
The Scala compiler detects tail recursion and replaces it with a jump back to the beginning of the function, after updating the function parameters with the new values.
The moral is that you should not shy away from using recursive algorithms to solve your problem. Often, a recursive solution is more elegant and concise than a loop-based one. If the solution is tail recursive, there won’t be any runtime overhead to be paid.
分享到:
相关推荐
尾递归的概念尾递归(Tail Recursion)的概念是递归概念的一个子集。对于普通的递归,由于必须要记住递归的调用堆栈,由此产生的耗用是难以估量的。比如下文中php小节第一个例子使用php写一个阶乘函数,就是由于递归...
使用C++非递归实现fibonacci数列,对正在学习算法的同学应该挺有帮助的
fibonacci数列的各种解法,递归、存储优化的递归、自下而上的递归(迭代法)、尾递归。其中分析内容请移步我的博客、
本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列,非常具有实用价值,需要的朋友可以参考下
fibonacci 递归求法
递归方法实现斐波那契数列
斐波那契函数 做好的程序 简单明了 无需更改 原创作品
Fibonacci数列的java实现,包括递归与非递归实现
C++实现Fibonacci数列递归及非递归算法
利用递归数列求解著名的Fibonacci数列的各项,用户可自定义输入要求的第n项,输入后即可求出从0到n每一项Fibonacci的值。
表达式C预言fibonacci函数非递归版
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者...
java递归实现斐波那契数列,实现n阶乘,实现1+2+3+...+n求和
华为题(斐波那契数列非递归)[定义].pdf
利用递归算法计算Fibnacci级数,基于C++语言
斐波那契递归.cpp
用Python轻松实现斐波那契数列——递归函数详解!
斐波那契数 尾递归 递归 循环 typedef int (*fabFunc)(int); int fabonacci(int n); int fabonacci1(int n);//递归 int fabonacci2(int n);//循环实现 int fabtrail(int n,int a,int b);//尾递归实现 void timing...
c#斐波那契数列(Fibonacci)(递归,非递归)实现代码,需要的朋友可以参考一下