StackOverFlow Exception in recursion calls

Question

Im trying out a bitwise And program for the range of number between a and b . Can have 'n' testcases for that.
0<=a,b<=2^32
1<=n<=200

EXPLANATION :
1
2 4
computation : 2&3&4

INPUT :
1
4009754624 4026531839

OUTPUT:
Exception in thread "main" java.lang.StackOverflowError at Example.BitwiseAnd.calculate(BitwiseAnd.java:78)

CODE :

public class BitwiseAnd
{
    static long temp = 0;
    static long result[];

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int time = scan.nextInt();
        if(validateTime(time))
        {
            result = new long[time];
            for(int i=0;i<time;i++)
            {
                long arr[] = new long[2];
                arr[0] = scan.nextLong();
                temp=arr[0];
                arr[1] = scan.nextLong();
                if(validateNum(arr[0],arr[1]))
                {
                    result[i] = calculateUsingRecursion(arr[0],arr[1]);
                    //result[i] = calculateUsingForLoop(arr[0],arr[1]);
                }
                else
                {
                    System.out.println("Enter a valid numbers");
                }
            }
            printResult(result);
        }
        else
        {
            System.out.println("Enter a valid number of testcases");
        }
    }

    public static void printResult(long[] result)
    {
        for(int i=0;i<result.length;i++)
        {
            System.out.println(result[i]);
        }
    }

    public static boolean validateNum(long num1, long num2)
    {
        Long max = (long)Math.pow(2, 32);
        if(num1<0 || num1>max)
        {
            return false;
        }
        else if(num2<0 || num2>max)
        {
            return false;
        }
        return true;
    }

    public static boolean validateTime(int time)
    {
        if(time<1 || time>200)
        {
            return false;
        }
        return true;
    }

    private static long calculateUsingRecursion(long num1, long num2)
    {
        while(num1<num2)
        {
            num1=num1+1;
            temp=temp&num1;
            calculateUsingRecursion(num1, num2);
        }
        return temp;
    }

    private static long calculateUsingForLoop(long num1,long num2)
    {
        num1=num1+1;
        for(long i=num1 ; i<=num2 ; i++)
        {
            temp=temp&num1;
        }
        return temp;
    }
}

the recursive method computation is throwing me StackOverFlowException , for large set of numbers. Whereas the for loop works fine . My question here is why couldn't we have recursion for the huge set of inputs? And how it could be fixed with recursion ?

It works with recursion, but you need enough memory to store the individual stackframes. In your case you can configure your JVM to provide more memory for this: https://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-size — C-Otto, Aug 28 '17 at 12:01
`"why couldn't we have recursion for the huge set of inputs"` - Because the call stack is finite. — David, Aug 28 '17 at 12:02
Doing that calculation requires recursing 16777215 times. You don't have enough resources to push that many frames into the stack. And, even if it were tail recursive (which it isn't), Java doesn't support tail call optimisation. — Andy Turner, Aug 28 '17 at 12:02
Make `temp` a local variable in both functions; imagine calling a function twice. Use the return value of the recursive call, use `if` instead of `while`. — Joop Eggen, Aug 28 '17 at 12:04
well you just know the answer, your computer can't afford the ram — Marco Salerno, Aug 28 '17 at 12:04

Adriaan Koster · Answer 1 · 2017-08-28T12:11:02.380

1

Your recursive function is sort of a mix between iterative and recursive. Change it like this:

private static long calculateUsingRecursion(long num1, long num2, long temp) {

    // Stop condition
    if (num1 >= num2) {
        return temp;
    }      

    // Progression
    num1 = num1 + 1;
    temp = temp & num1;

    // Recursion
    return calculateUsingRecursion(num1, num2, temp);        
}

Note that you will get a StackOverflowException if any recursive function recurses too deep.

edited Aug 28 '17 at 12:11

answered Aug 28 '17 at 12:09

Adriaan Koster

15,870
5
45
60

1

That'll still give stack overflow for large differences of `num2` and `num1`. – Andy Turner Aug 28 '17 at 12:10
Certainly, that's a problem with any recursive function. Maybe this is a homework assignment designed to demonstrate why recursive functions are not always applicable. – Adriaan Koster Aug 28 '17 at 12:11

feldim2425 · Accepted Answer · 2017-08-29T16:04:58.670

You didn't add all the infos (like a full stacktrace) and there is no BitwiseAnd.calculate method in your code.

1) You use a "while" in your Recursion method, but you should not loop because thats done by the recursive call, you should use a "if" instead.

2) The size of the stack is limited, so a method cannot call itself in an infinite loop. And with the inputs 4009754624 and 4026531839 it has to call itself 16777215 times. There is more ram needed for the background stuff. But to simplify it: Java has to allocate that 2 long arguments for your method 16777215 times and it can only reuse them after each method has returned.

So don't do recursive calls if you do many iterations.

DAle · Answer 3 · 2017-08-28T12:51:39.707

You don't need to iterate through all these numbers at all. You just need to find bits that are constant for all numbers in the interval (otherwise their AND equals to zero).

Let's iterate through the bits from highest to lowest and check that a and b have the same value of this bit. Stop iteration when they have different bits at some position:

long res = 0;
for (int bit = 32; bit >= 0; --bit) {
    long bita = a & (1L << bit);
    long bitb = b & (1L << bit);
    if (bita != bitb) break;
    res |= bita;
}

Runnable: https://ideone.com/pkrUtV

StackOverFlow Exception in recursion calls

3 Answers3