递归调用中的 StackOverFlow 异常

Question

我正在为 a 和 b 之间的数字范围尝试一个按位 And 程序。可以有 'n' 个测试用例。
0<=a,b<=2^32
1<=n<=200

解释 :
1
2 4
计算：2&3&4

输入 :
1
4009754624 4026531839

输出:
Exception in thread "main" java.lang.WhosebugError at Example.BitwiseAnd.calculate(BitwiseAnd.java:78)

代码：

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;
    }
}

对于大量数字，递归方法计算使我抛出 WhosebugException。而 for 循环工作正常。我的问题是为什么我们不能对大量输入进行递归？以及如何通过递归修复它？

Answer 1

你的递归函数是迭代和递归的混合体。像这样更改它：

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);        
}

请注意，如果任何递归函数递归得太深，您将得到 WhosebugException。

Answer 2

您没有添加所有信息（例如完整的堆栈跟踪）并且您的代码中没有 BitwiseAnd.calculate 方法。

1) 您在递归方法中使用了 "while"，但是您不应该循环，因为那是由递归调用完成的，您应该使用 "if"。

2) 栈的大小是有限的，所以一个方法不能在无限循环中调用自己。对于输入 4009754624 和 4026531839，它必须调用自己 16777215 次。背景内容需要更多内存。但为了简化它：Java 必须为您的方法分配 2 个长参数 16777215 次，并且它只能在每个方法返回后重用它们。

所以如果你做了很多次迭代就不要做递归调用。

Answer 3

您根本不需要遍历所有这些数字。您只需要找到区间内所有数字都不变的位（否则它们的 AND 等于零）。

让我们从最高位到最低位遍历这些位，并检查 a 和 b 是否具有相同的该位值。当它们在某个位置有不同的位时停止迭代：

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;
}

可运行：https://ideone.com/pkrUtV

递归调用中的 StackOverFlow 异常

StackOverFlow Exception in recursion calls

java

stack-overflow

iteration

recursion