CODEWITHSUNDEEP
javarecursioniterationstack-overflow
shashantrika
shashantrika

Reputation: 1089

StackOverFlow Exception in recursion calls

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 ?

Upvotes: 0

Views: 604

Answers (3)

feldim2425
feldim2425

Reputation: 424

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.

Upvotes: 1

DAle
DAle

Reputation: 9117

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

Upvotes: 1

Adriaan Koster
Adriaan Koster

Reputation: 16209

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.

Upvotes: 1

Related Questions