java - Java:计算自己的数据类型的斐波那契

This question already has answers here:

What causes a java.lang.StackOverflowError
                                
                                    （9个答案）
                                
                        
                                4年前关闭。
            
                    
我必须创建自己的BigInteger类的实现，该类称为GrosseZahl（德语为“ BigNumber”）。我已经实现了以下方法：


init()将整数或字符串转换为整数数组。
less(GrosseZahl value)如果此数字小于value，则返回true。
add(GrosseZahl summand)
mult(GrosseZahl factor)
toString()
equals(Object obj)


我要实现的最后一个方法是fib()，它计算此GrosseZahl的斐波那契数。我必须使用辅助方法来递归计算。

我最终得到了以下代码：

public GrosseZahl fib() {
    GrosseZahl f0 = new GrosseZahl(1);
    GrosseZahl f1 = new GrosseZahl(1);
    GrosseZahl counter = new GrosseZahl(1);

    return this.calcFib(f0, f1, counter);
}

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    if (this.equals(counter))
        return f1;

    counter = counter.add(new GrosseZahl(1));

    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

当我使用以下测试类测试该类时，出现堆栈溢出错误。

package java2;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class GrosseZahl_Test {

    GrosseZahl i0;
    GrosseZahl s0;
    GrosseZahl i1;
    GrosseZahl s1;
    GrosseZahl i55;
    GrosseZahl s55;
    GrosseZahl i60;
    GrosseZahl s60;
    GrosseZahl i99;
    GrosseZahl s99;
    GrosseZahl i100;
    GrosseZahl s100;
    GrosseZahl i12345;
    GrosseZahl s12345;
    GrosseZahl i47340;
    GrosseZahl s12345678901234567890;
    GrosseZahl s10345678901234567891;

    @Before
    public void setUp() throws Exception {
        i0 = new GrosseZahl(0);
        s0 = new GrosseZahl("0");
        i1 = new GrosseZahl(1);
        s1 = new GrosseZahl("1");
        i55 = new GrosseZahl(55);
        s55 = new GrosseZahl("55");
        i60 = new GrosseZahl(60);
        s60 = new GrosseZahl("60");
        i99 = new GrosseZahl(99);
        s99 = new GrosseZahl("99");
        i100 = new GrosseZahl(100);
        s100 = new GrosseZahl("100");
        i12345 = new GrosseZahl(12345);
        s12345 = new GrosseZahl("12345");
        i47340 = new GrosseZahl(47340);
        s12345678901234567890 = new GrosseZahl("12345678901234567890");
        s10345678901234567891 = new GrosseZahl("10345678901234567891");
    }

    /* ... */

    @Test
    public void testFib() {
        assertEquals("1", new GrosseZahl(0).fib().toString());
        assertEquals("1", new GrosseZahl(1).fib().toString());
        assertEquals("2", new GrosseZahl(2).fib().toString());
        assertEquals("3", new GrosseZahl(3).fib().toString());
        assertEquals("5", new GrosseZahl(4).fib().toString());
        assertEquals("8", new GrosseZahl(5).fib().toString());
        assertEquals("89", new GrosseZahl(10).fib().toString());
        assertEquals("1346269", new GrosseZahl(30).fib().toString());
    }

}

堆栈溢出错误消息：

java.lang.StackOverflowError
    at java.util.regex.Pattern.sequence(Pattern.java:2134)
    at java.util.regex.Pattern.expr(Pattern.java:1996)
    at java.util.regex.Pattern.group0(Pattern.java:2827)
    at java.util.regex.Pattern.sequence(Pattern.java:2051)
    at java.util.regex.Pattern.expr(Pattern.java:1996)
    at java.util.regex.Pattern.compile(Pattern.java:1696)
    at java.util.regex.Pattern.<init>(Pattern.java:1351)
    at java.util.regex.Pattern.compile(Pattern.java:1028)
    at java.lang.String.replaceFirst(String.java:2166)
    at java2.GrosseZahl.init(GrosseZahl.java:38)
    at java2.GrosseZahl.<init>(GrosseZahl.java:25)
    at java2.GrosseZahl.add(GrosseZahl.java:112)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:158)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    /* ... */

更新：我进行了一些研究，发现运行测试（0）时，在calcFib(...)方法中始终是GrosseZahl_Test。因此它永远不会等于计数器，因此if语句永远不会为真。但是为什么this总是0？如果在if语句上方插入System.out.println(this)并运行测试，则可以自己进行测试：

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    System.out.println(this);

    if (this.equals(counter))
        return f1;

    counter = counter.add(new GrosseZahl(1));

    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

如果我使用less()方法而不是equals()，它将起作用：

public GrosseZahl fib() {
    GrosseZahl f0 = GrosseZahl.ONE;
    GrosseZahl f1 = GrosseZahl.ONE;
    GrosseZahl counter = new GrosseZahl(2);

    return this.calcFib(f0, f1, counter);
}

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    System.out.println(this);

    if (this.less(counter))
        return f1;

    counter = counter.add(GrosseZahl.ONE);
    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

这是GrosseZahl类的所有代码：

package java2;

import java.util.Arrays;

public class GrosseZahl {

    private int[] digits;
    private int length;
    private String value;

    public GrosseZahl(int value) {
        this.value = Integer.toString(value);
        this.init();
    }

    public GrosseZahl(String value) {
        this.value = value;
        this.init();
    }

    private void init() throws NumberFormatException {
        String[] digits;
        String value = this.value;

        if (value.charAt(0) == '-')
            throw new NumberFormatException("Number must be non-negative.");

        if (!value.matches("\\d+"))
            throw new NumberFormatException("Number must only contain digits.");

        value = value.replaceFirst("^0+(?!$)", "");
        digits = value.split("");

        this.length = digits.length;
        this.digits = new int[this.length];

        for (int i = 0; i < this.length; i++) {
            this.digits[i] = Integer.parseInt(digits[i]);
        }
    }

    public boolean less(GrosseZahl value) {
        if (this.length < value.length)
            return true;

        if (this.length == value.length)
            for (int i = 0; i < this.length; i++) {
                if (this.digits[i] < value.digits[i])
                    return true;
                if (this.digits[i] > value.digits[i])
                    return false;
            }

        return false;
    }

    public GrosseZahl add(GrosseZahl summand) {
        GrosseZahl a;
        GrosseZahl b;
        GrosseZahl result;
        StringBuilder number;
        int carry;
        int offset;
        int sum;

        if (!this.less(summand)) {
            a = this;
            b = summand;
        } else {
            a = summand;
            b = this;
        }

        offset = a.length - b.length;
        carry = 0;
        number = new StringBuilder();

        for (int i = a.length - 1; i >= 0; i--) {
            sum = a.digits[i] + carry;

            if (i >= offset)
                sum += b.digits[i - offset];

            if (sum > 9)
                carry = 1;
            else
                carry = 0;

            /*
             * We append the digit because it uses less memory than prepending.
             */
            number.append(sum % 10);
        }

        /*
         * If carry is still one we need to append an one.
         */
        if (carry == 1) {
            number.append(1);
        }

        /*
         * Since we’ve appended the numbers we need to reverse the order.
         */
        result = new GrosseZahl(number.reverse().toString());

        return result;
    }

    public GrosseZahl mult(GrosseZahl factor) {
        GrosseZahl a;
        GrosseZahl b;
        GrosseZahl result;

        a = this;
        b = factor;
        result = new GrosseZahl(0);

        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < b.length; j++) {
                int zeroes = a.length - i + b.length - j - 2;
                int c = a.digits[i] * b.digits[j];

                StringBuilder sum = new StringBuilder();

                sum.append(c);

                for (int k = 0; k < zeroes; k++)
                    sum.append(0);

                result = result.add(new GrosseZahl(sum.toString()));
            }

        return result;
    }

    public GrosseZahl fib() {
        GrosseZahl f0 = new GrosseZahl(1);
        GrosseZahl f1 = new GrosseZahl(1);
        GrosseZahl counter = new GrosseZahl(1);

        return this.calcFib(f0, f1, counter);
    }

    private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
        GrosseZahl f2;

        if (this.equals(counter))
            return f1;

        counter = counter.add(new GrosseZahl(1));

        f2 = f0.add(f1);
        f0 = f1;

        return calcFib(f1, f2, counter);
    }

    @Override
    public String toString() {
        StringBuilder number = new StringBuilder();

        for (int digit : digits)
            number.append(digit);

        return number.toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        GrosseZahl other = (GrosseZahl) obj;
        if (!Arrays.equals(digits, other.digits))
            return false;
        if (length != other.length)
            return false;
        return true;
    }

}

最佳答案

在Java中，可以使用两种类型的逻辑空间：使用new关键字分配的堆；使用java2.GrosseZahl#calcFib关键字分配的堆。和堆栈。要执行Java中的任何指令，必须将操作数压入堆栈，并且在操作完成后，结果将替换堆栈上的操作数。对于每次方法调用，您都将参数推入堆栈，直到方法返回时才将其删除。

上面的问题是您尝试在方法 / 3中递归使用堆栈。解决此问题的常用方法是将算法转换为使用堆空间，该堆空间具有更多可用空间。