tail Recursion multiplication using BigInteger

Question

I am trying to modify my multiplication by addition function to incorporate two things:-

(1) tail recursion (2) bigIntegers

However, for large integers I am still struggling since I got a stack overflow. I even tried to run my program using a -Xss switch to expand the stack but still no luck. I think there is something wrong with my method. Appreciate any advice.

<!-- language-all: lang-java -->
public static BigInteger multiRecursive(int multiplicand, int multiplier) {
    return multiTailRecursive(multiplicand, multiplier, multiplicand);
}

public static BigInteger multiTailRecursive(int multiplicand, int multiplier, int result){      
    if (multiplicand == 0 || multiplier == 0) {
        return BigInteger.valueOf(0);
    }
    if (multiplier == 1) {
        return BigInteger.valueOf(result);
    }

    return multiTailRecursive(multiplicand, multiplier - 1, result + multiplicand);
}

Why? Did you know Java does not support [tail recursion optimization](http://stackoverflow.com/a/4401090/2970947)? — Elliott Frisch, Apr 28 '14 at 00:11
possible duplicate of [Stack overflows from deep recursion in Java?](http://stackoverflow.com/questions/860550/stack-overflows-from-deep-recursion-in-java) — s16h, Apr 28 '14 at 00:13
No I actually didn't know that, however, when I used a regular recursion method without the tail recursion and I used the Xss switch to run the program I was able to multiply 50000 * 50000 recursively and get a result...however, now the function returns a negative number....am guessing a stack overflow... — Cola4ever, Apr 28 '14 at 00:13

score 1 · Accepted Answer · edited May 23 '17 at 10:33

1

This issue has already been discussed at Stack overflows from deep recursion in Java?:

Increasing the stack size will only serve as a temporary bandage ... what you really want is tail call elimination, and Java does not have this for various reasons.

edited May 23 '17 at 10:33

Community

1
1

answered Apr 28 '14 at 00:13

s16h

4,647
1
21
33

Are my functions correct though? and why if I increase the stack size I still get an error? – Cola4ever Apr 28 '14 at 00:31

tail Recursion multiplication using BigInteger

1 Answers1