代码之家 › 专栏 › 技术社区 › user8581108

计算n=11000+带记忆的斐波那契递归方法时堆栈溢出

memoization fibonacci stack-overflow recursion java

user8581108 · 技术社区 · 8 年前

public class BigInt {

static BigInteger[] fval;

public static void main(String[] args) {
    int index;
    Scanner input = new Scanner(System.in);
    index = input.nextInt();
    fval = new BigInteger[index + 1];

    System.out.println(fib_rec(index));
}

public static BigInteger fib_rec(int index) {
    BigInteger result = BigInteger.ONE;
    if (index <= 2) {
        return result;
    } else {
        if (fval[index] != null) {
            result = fval[index];
        } else {
            result = fib_rec(index - 1).add(fib_rec(index - 2));
            fval[index] = result;
        }
        return result;
    }
}

4 回复 | 直到 6 年前

Don Hosek 8 年前

你的记忆不会改变递归的深度。。。关于呼叫 fib_rec(n) ,它调用 fib_rec(n-1) 哪些电话 fib_rec(n-2) fib_rec(index - 2).add(fib_rec(index - 1))

然而,如果不对算法进行更剧烈的重写,就无法避免堆栈深度问题。

Indra Basak 8 年前

public class BigInt {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int index = input.nextInt();

        System.out.println(fib_rec(index));
    }

    public static BigInteger fib_rec(int index) {
        if (index <= 2) {
            return BigInteger.ONE;
        }

        BigInteger[] fval = new BigInteger[index + 1];
        fval[0] = BigInteger.ONE;
        fval[1] = BigInteger.ONE;

        for (int i = 2; i <= n; i++) {
            fval[i] = fval[i-1].add(fval[i-2]);
        } 

        return fval[n];
   }
}

}

Turing85 Oleksandr Pyrohov 8 年前

不可避免的

这个 StackOverflowError Java does not have tail call optimization . 其次,对于每个递归调用,Java必须分配一些内存,例如参数。即使方法没有参数,Java也需要一点内存来存储方法调用结束后要跳转到的地址。因此,你最终会耗尽你的记忆,无论有多大。通过使用更多的堆栈内存启动JVM,可以延长不可避免的时间。可以找到该选项(以及其他一些选项) here .

我们能做得更好吗?

是的,我们可以。但不是使用递归算法。我们需要将这个递归算法转化为迭代算法。事实上 each recursion can be transformed in an iteration ans vice-versa

int fibonacci(int nth)
    if nth is smaller than 0
        then halt and catch fire

    if nth is smaller than 2
        then return nth

    int last <- 1
    int secondToLast <- 0;

    for (int ith <- 2; ith less or equal to nth, increment ith)
        int tmp <- last + secondToLast
        secondToLast <- last
        last <- tmp
    end for

    return last;

上述算法具有线性时间复杂度(假设加法可以在恒定时间内完成)和恒定内存复杂度,因此可以解决您的问题。

Feras Wilson 8 年前

出现堆栈溢出的原因是内存不足。增加可用内存,特别是堆栈大小。只需添加或者你喜欢什么尺寸。

处理这种情况的最佳方法是实际使用更好的算法,这样就不需要消耗大量内存。