java - 在 Java 中使用 BigInteger 递归生成 Lucas 系列

Question

我正在尝试使用递归和 BigInteger 类将 Lucas 系列写入代码，但我在设置基本情况时遇到了问题。这段代码正确地输出了斐波那契数列，但是我尝试将起始值 N(0) 和 N(1) 分别设为 2 和 1 的所有操作都完全失败了。我搜索了帮助文件，但没有发现使用 BigIntegers 完成的，我将需要它，因为我确实计划远远超过 int 限制。

import java.math.BigInteger;

public class LucasSeries {

    private static BigInteger TWO = BigInteger.valueOf(2);

    public static BigInteger fibonacci(BigInteger number) {
        if (number.equals(BigInteger.ZERO) || number.equals(BigInteger.ONE)) {
            return number;
        } else {
            return fibonacci(number.subtract(BigInteger.ONE)).add(fibonacci(number.subtract(TWO))); 
        }
    }

    public static void main(String[] args) {
        for (int counter = 0; counter <= 30; counter++) {
           System.out.printf("Lucas of %d is: %d%n", counter,
                fibonacci(BigInteger.valueOf(counter)));
        }
    }
}

Answer 1

有两个基本情况 N(0) 和 N(1)。您可以组合这些，但代码更接近于 the series definition如果您分别处理它们，如:

public static BigInteger fibonacci(BigInteger number) {
    if (number.equals(BigInteger.ZERO))
        return TWO;

    if(number.equals(BigInteger.ONE))
        return BigInteger.ONE;

    return fibonacci(number.subtract(BigInteger.ONE)).add(
            fibonacci(number.subtract(TWO)));
}

它产生以下输出:

Lucas of 0 is: 2
Lucas of 1 is: 1
Lucas of 2 is: 3
Lucas of 3 is: 4
Lucas of 4 is: 7
Lucas of 5 is: 11
Lucas of 6 is: 18
Lucas of 7 is: 29
Lucas of 8 is: 47
// Remainer omitted