CODEWITHSUNDEEP
javarecursionbigintegerfibonacci
F.Helix
F.Helix

Reputation: 47

Producing the Lucas series recusively using BigInteger in Java

I'm trying to get the Lucas series into code using recursion and the BigInteger class, but I'm having trouble setting the base cases. This code correctly outputs the Fibonacci sequence, but everything I've tried to get the starting values, N(0) and N(1) to 2 and 1, respectively, have failed entirely. I've searched help files but nothing I've found has done it using BigIntegers, which I'll be needing as I do plan to go well above the int limit. 

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)));
        }
    }
}

Upvotes: 1

Views: 348

Answers (2)

Austin
Austin

Reputation: 8585

There's two base cases N(0) and N(1). You can combine these, but the code more closely matches the series definition if you handle them separately, as in:

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)));
}

It produces the following output:

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

Upvotes: 3

maraca
maraca

Reputation: 8753

Instead of

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

just return

if (number.equals(BigInteger.ZERO) || number.equals(BigInteger.ONE)) {
    return TWO.subtract(number);

that's all.

Upvotes: 2

Related Questions