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: stackoverflow.com/questions/3700459/… — C-Otto
– C-Otto, Commented Aug 28, 2017 at 12:01
"why couldn't we have recursion for the huge set of inputs" - Because the call stack is finite. — David
– David, Commented Aug 28, 2017 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
– Andy Turner, Commented Aug 28, 2017 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
– Joop Eggen, Commented Aug 28, 2017 at 12:04

feldim2425 · Accepted Answer · 2017-08-29 16:04:58Z

1

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.

edited Aug 29, 2017 at 16:04

answered Aug 28, 2017 at 12:22

feldim2425

4244 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Adriaan Koster · Accepted Answer · 2017-08-28 12:11:02Z

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, 2017 at 12:11

answered Aug 28, 2017 at 12:09

Adriaan Koster

16.3k5 gold badges51 silver badges64 bronze badges

2 Comments

Andy Turner Over a year ago

That'll still give stack overflow for large differences of num2 and num1.

Adriaan Koster Over a year ago

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.

DAle · Accepted Answer · 2017-08-28 12:51:39Z

1

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

edited Aug 28, 2017 at 12:51

answered Aug 28, 2017 at 12:26

DAle

9,1922 gold badges28 silver badges48 bronze badges

Collectives™ on Stack Overflow

StackOverFlow Exception in recursion calls

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related