java – 递归Fibonacci代码

发布时间：2020-12-15 05:13:45 所属栏目：Java 来源：网络整理

导读：我写了斐波纳契系列如下. 我想知道以下是否是使用递归的正确方法,因为我认为我正在循环使用条件的fibonacci函数并且每次都像for循环一样递增i的值. public class FibanocciSeriesImpl {static int a,b,i,n; static { a=0; b=1;i=2; Scanner sc=new Scanner(S

我写了斐波纳契系列如下.
我想知道以下是否是使用递归的正确方法,因为我认为我正在循环使用条件的fibonacci函数并且每次都像for循环一样递增i的值.

public class FibanocciSeriesImpl {
static int a,b,i,n;
    static
    {
        a=0; b=1;i=2;
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number of elements in the series");
        n=sc.nextInt();

    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("The fibnocci series is below");
        System.out.print(a+","+b);
        fibnocciImpl(a,b);
    }
    public static void fibnocciImpl(int a,int b)
    {
        int c=a+b;
        a=b;
        b=c;
        i++;
        System.out.print(","+c);
        if(i<n)
        fibnocciImpl(a,b);

    }
}

解决方法

虽然已多次说过,但值得重复一下：递归计算Fibonacci序列—通过定义而不使用,例如 memoization —需要指数时间( something like O(1.6 ^ n)),这是不可行的对于大n(例如,对于n> 40).

Fibonacci序列也可以在线性时间迭代计算：

public static long fib(int n) {
    long a = 0,b = 1;
    if (n <= 1) { return n; }
    for (int i = 2; i < n; ++i) {
        int tmp = b;
        b += a;
        a = tmp;
    }
    return b;
}

对于它的价值,这是Brainfuck中的相同算法(从我高中时代开始:-)：

++++++++++ > + ; N i j 
< ; point to N 
[
    > ; move pointer to i
    [ >> + > + <<< - ] ; add i to t1 and t2
    > ; move to j
    [ < + > - ] ; add j i 
    >> ; move to t2
    [ << + >> - ] ; add t2 to j 
    < ; move to t1
    [ >> + << - ] ; add t1 to t3
    >> ; move to t3 
    [ < + < + >> - ] ; move t3 to t1 and t2
    <<<<< -
]
>>> .

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!