使用递归斐波那契函数时出现堆栈溢出错误

发布于 2025-01-05 19:28:30 字数 405 浏览 0 评论 0原文

这是我的代码，它在 400 到 4000 的值下运行良好，但一旦达到大约 400 万，我就会收到堆栈溢出错误。

提前致谢！

public class Fib {
static int c=1,b=2;
static long sum1=0,sum2=0;

static long fib(long a){
if(a==1){
    return 1;
}
if(a==2){
    return 2;
}
else{
    return fib(a-1)+fib(a-2);
}

    }


    public static void main(String[] args){
sum2= fib(4000000);
    System.out.println("Sum %f" +sum2);
}
    }

原文

Here's my code and it runs well with values of 400 to 4000 but once it's about 4mil, I get stack overflow errors.

Thanks in advance!

public class Fib {
static int c=1,b=2;
static long sum1=0,sum2=0;

static long fib(long a){
if(a==1){
    return 1;
}
if(a==2){
    return 2;
}
else{
    return fib(a-1)+fib(a-2);
}

    }


    public static void main(String[] args){
sum2= fib(4000000);
    System.out.println("Sum %f" +sum2);
}
    }

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不美如何 2025-01-12 19:28:30

是的 - 你的堆栈空间已经用完了。它远非无限，并且您在每次递归调用中都会使用它。您试图最终得到一个包含 400 万个堆栈帧的堆栈 - 这是行不通的。

我建议您考虑迭代方法。即使你有无限数量的堆栈，该代码也可能在宇宙热寂之前无法完成。（想想这段代码的复杂性......）

回复收藏 0 原文

懒猫 2025-01-12 19:28:30

您可以增加 Java 程序的堆栈大小。示例：

java -Xss4m YourProgram

参考

尽管如此，我也推荐一种迭代方法。

You can increase the stack size of Java programs. Example:

java -Xss4m YourProgram

Reference

Nevertheless I would also recommend an iterative method.

回复收藏 0 原文

旧梦荧光笔 2025-01-12 19:28:30

正如 Jon Skeet 上面提到的，你的代码需要大量的时间来运行 - 2 到 400 万，这在任何方面都是不切实际的。坦率地说，我很惊讶堆栈根本就干涸了，我认为代码只会运行一段荒谬的时间。

您应该使用迭代方法。这是斐波那契数列的更好实现：

static long fib(long i){
    if ( i == 0 || i == 1 ) return 1;
    long a = 1; //This is the 0th element 
    long b = 1; //This is the 1st element
    while( i-- > 1 ){ //Each iteration, sets a and b to the next element in the fibonacci sequence
        long temp = b;
        a += b;
        b = a;
        a = temp;
    }
    return b;
}

As Jon Skeet above mentioned, your code would require a huge amount of time to run - 2 to the 4 million, which is not practical in any way. Frankly i'm surprised the stack ran dry at all, I'd think the code would just run for a ridiculous amount of time.

You should use an iterative approach. Here's a nicer implementation of the fibonacci sequence:

static long fib(long i){
    if ( i == 0 || i == 1 ) return 1;
    long a = 1; //This is the 0th element 
    long b = 1; //This is the 1st element
    while( i-- > 1 ){ //Each iteration, sets a and b to the next element in the fibonacci sequence
        long temp = b;
        a += b;
        b = a;
        a = temp;
    }
    return b;
}

回复收藏 0 原文

~没有更多了~