原创

实现斐波那契数列算法-递归和非递归

温馨提示:
本文最后更新于 2020年09月08日,已超过 756 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

斐波那契数列:

        斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........

这个数列从第3项开始,每一项都等于前两项之和。

代码:

以下是用java代码实现的斐波那契数列的递归与非递归算法

package com.bug1;
public class Main {
    public static void main(String[] args) {
        System.out.println("递归实现斐波那契数列");
        System.out.println(fib(4));
        System.out.println("非递归实现斐波那契数列");
        System.out.println(fib2(4));
    }
    /*
     * n=    1 2 3 4 5 6 7 
     * sum=  1 1 2 3 5 8 
     * 
     * */
    //递归实现斐波那契数列
    public static int fib(int n) {
        if(n<=2)return 1;
        return fib(n-1)+fib(n-2);        
    }
    //非递归实现斐波那契数列
public static int fib2(int n) {
    if(n<=2)return 1;
    int first=1;
    int second=1;
    int sum=0;
    while(n>2) {
    sum=first+second;
    first=second;
    second=sum;
    n--;
    }    
    return second;
}    
}

运行结果:

正文到此结束
本文目录