使用Recursion的StackOverflowError

Question

我应该比较一个递归函数和一个非递归函数,看看哪个类项目更快.当迭代器等于10,100,1000等时,教授还希望我们以毫秒为单位计算迭代次数.我得到了所有工作,但是在C++中获得计时器时遇到了很多麻烦,所以我切换到了Java,因为它太多了更容易获得毫秒输出.

但是现在当我尝试使用超过8,000的任何数字时,我从递归算法中得到了一个很大的堆栈溢出错误.任何人都可以给我任何见解吗？额外:我也无法弄清楚如何在递归函数中执行计时器,就像我在Non-Recursive中一样.我该如何处理？

public class comparingTimes {
    public static void main(String[] args) {

        double num = 10000;
        double result;
        nonRec(num); 
        result = rec(num);      
        System.out.printf("Rec %.0f",(result));
    }
    public static void nonRec(double num)
    {
    double resultNum = 1;
    double total = 0;
    long startTime = System.currentTimeMillis();
    long endTime;
    for (double i = 1; i < num; i++)
     {
        total += i * (i+1);
        if (i == resultNum)
        {
            endTime = System.currentTimeMillis();
            System.out.printf("Total execution time: %f seconds - num = %.0f%n", (endTime - startTime)/1000.0, i);
            resultNum *= 10;
        }           
     }      
    System.out.printf("NonRec: %.0f%n", total); 
}
public static double rec(double num)
{
    if (num == 0)
        return 0;
    else            
        return num * (num-1) + rec(num-1);      
}
}

Answer 1

递归的理想用例是在每个递归级别上大量减少"搜索空间".例如,考虑二进制搜索,其中每个递归级别将剩余的搜索空间减半.

你的特殊问题是你正在尝试进行8000级递归,因为每个级别只是减少了值.这将需要相当大的堆栈空间.

您可以考虑使用-ss或-oss选项增加JVM的堆栈大小(当然,取决于实现).但那只会给你这么多买.

就整个递归操作的计时而言,我只是将时间存储在顶级调用之前main(),然后将其与顶级调用返回之后的时间进行比较,如:

long startTime = System.currentTimeMillis();
result = rec(num);
long endTime = System.currentTimeMillis();
// Now calculate the elapsed time.

没有必要尝试在递归调用本身内执行此操作.

如果你想在某些点做内的递归调用,您可以初始化一个"全局"计数器变量(一个递归本身,如类级别静态变量外)为0,并有递归函数增加它的每递归水平.

然后让它输出您感兴趣的点的时间增量,例如当变量设置为10,100,1000等时.