admin管理员组

文章数量:1031308

【Java实战】——手撕斐波那契数列

1.什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割数列 [1]，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：0、1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

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

2.代码实现

2.1 递归实现

递归是一种直接或间接调用自身的编程技术。根据斐波那契数列的定义，我们可以很容易地使用递归方法来实现。

代码语言：javascript代码运行次数：0运行复制
public class Test {
    public static int fib(int n) {
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        int tmp = fib(n - 1) + fib(n - 2);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
        System.out.println(fib(6));
    }
}

递归实现的优缺点：

  • 优点：代码简洁直观，符合斐波那契数列的数学定义，易于理解。
  • 缺点：存在大量的重复计算，时间复杂度较高（约为 O(2^n)），当 n 较大时，程序运行效率极低，甚至可能导致栈溢出错误。

2.2 迭代实现

迭代是通过循环的方式，逐步计算出每一项的值。相比于递归，迭代方式可以避免重复计算，提高效率。

代码语言：javascript代码运行次数：0运行复制
public class Test {
    public static int fib(int n){
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        int f1 = 0;
        int f2 = 1;
        int f3 = 0;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
    public static void main(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
        System.out.println(fib(6));
    }
}

迭代实现的优缺点：

  • 优点：时间复杂度为 O(n)，避免了递归的重复计算，效率更高，不会出现栈溢出问题。
  • 缺点：代码相对递归方式稍显复杂，理解起来可能需要更多时间。

3.执行结果

【总结】

  • 本文介绍了斐波那契数列的基本概念，并通过Java语言展示了两种不同的实现方式：递归和迭代实现。每种方式都有其特点和适用场景
  • 在实际编程中，我们可以根据具体需求选择合适的实现方式，以达到最优的性能和效果。
  • 希望通过本文的介绍，你对斐波那契数列及其Java实现有了更深入的理解和掌握！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-11，如有侵权请联系 cloudcommunity@tencent 删除递归数学效率javasystem

【Java实战】——手撕斐波那契数列

1.什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割数列 [1]，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：0、1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

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

2.代码实现

2.1 递归实现

递归是一种直接或间接调用自身的编程技术。根据斐波那契数列的定义，我们可以很容易地使用递归方法来实现。

代码语言：javascript代码运行次数：0运行复制
public class Test {
    public static int fib(int n) {
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        int tmp = fib(n - 1) + fib(n - 2);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
        System.out.println(fib(6));
    }
}

递归实现的优缺点：

  • 优点：代码简洁直观，符合斐波那契数列的数学定义，易于理解。
  • 缺点：存在大量的重复计算，时间复杂度较高（约为 O(2^n)），当 n 较大时，程序运行效率极低，甚至可能导致栈溢出错误。

2.2 迭代实现

迭代是通过循环的方式，逐步计算出每一项的值。相比于递归，迭代方式可以避免重复计算，提高效率。

代码语言：javascript代码运行次数：0运行复制
public class Test {
    public static int fib(int n){
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        int f1 = 0;
        int f2 = 1;
        int f3 = 0;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
    public static void main(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
        System.out.println(fib(6));
    }
}

迭代实现的优缺点：

  • 优点：时间复杂度为 O(n)，避免了递归的重复计算，效率更高，不会出现栈溢出问题。
  • 缺点：代码相对递归方式稍显复杂，理解起来可能需要更多时间。

3.执行结果

【总结】

  • 本文介绍了斐波那契数列的基本概念，并通过Java语言展示了两种不同的实现方式：递归和迭代实现。每种方式都有其特点和适用场景
  • 在实际编程中，我们可以根据具体需求选择合适的实现方式，以达到最优的性能和效果。
  • 希望通过本文的介绍，你对斐波那契数列及其Java实现有了更深入的理解和掌握！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-11，如有侵权请联系 cloudcommunity@tencent 删除递归数学效率javasystem

本文标签： Java实战手撕斐波那契数列

版权声明：本文标题：【Java实战】——手撕斐波那契数列 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747725446a2209380.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。