Using Java to reduce BigIntegers using recursion. The method reduces the number completely, then loops to the number 'upwards' for unknown reasons

Question

My assignment is write a method that reduces a BigInteger using recursion. If the number is even, split it in half then repeat the process, if the number is odd, then multiply it by 3, add 1, and repeat the process, while keeping track of the number of times this happens.

The recursion continues until the number reaches 1, then I return the amount of times this process has occurred.

I think my methods should work fine. They don't. They reduce the BigInteger to 1, then it begins looping upwards to a random number. I don't understand why. Any help would be appreciated.

EDIT: What I mean by 'looping upwards': After the big int is reduced to 1, the method continues 'looping' and every time it loops, the number grows, also the counter diminishes as the method loops. There's nothing in the method to account for that so I don't know why it does it. That explanation doesn't really help, but I put SystemPrintLn's everywhere and saw it do it.

public int Problem9(BigInteger value) {
    BigInteger zero = BigInteger.valueOf(0);
    BigInteger one = BigInteger.valueOf(1);
    BigInteger two = BigInteger.valueOf(2);
    BigInteger three = BigInteger.valueOf(3);

    int count = reduceBigInt(value, zero, one, two, three, 1);
    
    return count;
}
public int reduceBigInt(BigInteger num, BigInteger zero,
        BigInteger one, BigInteger two, BigInteger three, int i) {
    
    if (num.equals(one))
        return i;
    else if ((num.remainder(two)) == zero)
        reduceBigInt((num.divide(two)), zero, one, two, three, i++);
    else
        reduceBigInt((num.multiply(three).add(one)), zero, one, two, three, i++);
    return i;
}

Answer 1

There are a few issues:

• The argument i++ will pass the original value of i (before increment), which means that every recursive call will receive the same value for their local i, which is 1. When the recursive call comes back, the next statement will do return i, when at that time i has been incremented once (remember it is a local variable), and so that return will always return 2.

• Although the recursive calls return a value, this value is ignored by the caller making the recursive call.

• == zero is not the way to compare BigIntegers. In this particular case, you could use the testBit method instead.

• As you start out with i equal to 1, your function could never return 0, yet when the input is 1 the response should be 0.

• It is a pity you have to pass zero, one, two and three over and over again as argument, consuming stack space. Instead, define them as fields. You can even get rid of all of them:

  • Instead of equals(one) you can use bitLength() as only 1 has a bit length of 1.
  • Instead of mod(two) and compare with zero, use testBit(0)
  • instead of divide(two), use shiftRight(1)
  • Instead of multiply(three), simply add num to itself twice, and to add the one we can do that after the first addition by flipping the least bit (which is guaranteed to be zero as we just doubled the number).

• If you decide to use recursion, then it is more elegant to not pass i as argument, but to have each recursive call execute as if it was the top-level execution -- without needing information of what was already counted before. In that approach, the base case should return 0, and the caller should add one to the returned value from recursion.

Here is how you could do that:

    public int Problem9(BigInteger num) {
        return num.bitLength() == 1 ? 0 // Base case
             : 1 + Problem9(
                 num.testBit(0) ? num.add(num).flipBit(0).add(num) // 3x+1
                                : num.shiftRight(1) // x/2
               );
    }

Answer 2

"... If the number is even, split it in half then repeat the process, if the number is odd, then multiply it by 3, add 1, and repeat the process, while keeping track of the number of times this happens. ..."

Here is an example.

The BigInteger class conveniently offers instances for common values, ZERO, ONE, TWO, etc.

import static java.math.BigInteger.*;

class Mutate {
    BigInteger three = new BigInteger("3");
    int n = 0;

    void f(BigInteger x) {
        if (x.compareTo(ONE) == 0) return;
        n++;
        if (x.mod(TWO).compareTo(BigInteger.ZERO) == 0) f(x.divide(TWO));
        else f(x.multiply(three).add(ONE));
    }
}

The result of f(new BigInteger("123")) would be 46.
Here is an output.

n = 0, x = 123
n = 1, x = 370
n = 2, x = 185
n = 3, x = 556
n = 4, x = 278
n = 5, x = 139
n = 6, x = 418
n = 7, x = 209
n = 8, x = 628
n = 9, x = 314
n = 10, x = 157
n = 11, x = 472
n = 12, x = 236
n = 13, x = 118
n = 14, x = 59
n = 15, x = 178
n = 16, x = 89
n = 17, x = 268
n = 18, x = 134
n = 19, x = 67
n = 20, x = 202
n = 21, x = 101
n = 22, x = 304
n = 23, x = 152
n = 24, x = 76
n = 25, x = 38
n = 26, x = 19
n = 27, x = 58
n = 28, x = 29
n = 29, x = 88
n = 30, x = 44
n = 31, x = 22
n = 32, x = 11
n = 33, x = 34
n = 34, x = 17
n = 35, x = 52
n = 36, x = 26
n = 37, x = 13
n = 38, x = 40
n = 39, x = 20
n = 40, x = 10
n = 41, x = 5
n = 42, x = 16
n = 43, x = 8
n = 44, x = 4
n = 45, x = 2
n = 46, x = 1