0

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

但是现在当我尝试使用任何超过 8,000 的数字时，我会从递归算法中得到一个大的胖堆栈溢出错误。谁能给我任何见解？奖励：我也不知道如何像在非递归函数中那样在递归函数中执行计时器。我将如何处理这个？

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

2 回答 2

5

递归的理想用例是在每个递归级别上大量减少“搜索空间”。例如，考虑一个二分搜索，其中每个递归级别将剩余搜索空间减半。

您的特殊问题是您正在尝试进行 8000 级递归，因为每个级别都会简单地递减值。这将需要相当大的堆栈空间。

您可以考虑使用-ssor-oss选项增加 JVM 的堆栈大小（当然取决于实现）。但这只会给你买这么多。

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

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

无需尝试在递归调用本身中执行此操作。

如果您想在递归调用中的某些点执行此操作，您可以将“全局”计数器变量（递归本身之外的一个，例如类级静态变量）初始化为 0，并让递归函数为每个递归级别。

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

于 2013-01-30T04:37:38.823 回答
0

尝试增加堆栈大小。

至于测量时间

public static void main(String[] args) {

    double num = 10000;
    double result;
    long start = System.currentTimeMillis();
    nonRec(num); 
    long finish = System.currentTimeMillis();
    System.out.println("Time taken (non-recursive): " + (finish -start));
    start = System.currentTimeMillis();
    result = rec(num);      
    finish = System.currentTimeMillis();
    System.out.println("Time taken (recursive): " + (finish -start));
    System.out.printf("Rec %.0f",(result));
}
于 2013-01-30T05:31:37.507 回答