StackOverflowError using Recursion

Question

I'm supposed to be comparing a Recursive and a Non-Recursive function to see which one is quicker for a class project. The professor also wants us to time the iterations in milliseconds when the iterator is equal to 10,100,1000, etc. I got it all to work but was having loads of trouble in C++ getting the timer, so I switched to Java as it's much much easier to get millisecond output.

But now when I try to use any number over 8,000 I get a big fat stack overflow error from the Recursive algorithm. Can anyone give me any insight? Bonus: I also can't figure out how to do the timer in the Recursive function like I did in the Non-Recursive. How would I approach this?

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

Having ` == 0` is always risky and that is the problem you have here. Change the type to an `int`. — BevynQ, Jan 30 '13 at 04:35
@BevynQ All int values are exactly representable in double. There is no rounding involved in subtracting 1 from a double that represents an int. I think the problem is more likely to be stack space. — Patricia Shanahan, Jan 30 '13 at 04:52
@PatriciaShanahan: is *ALWAYS* correct. This is something you (BevynQ) will have to get used to I'm afraid. 1+ to Patricia. — Hovercraft Full Of Eels, Jan 30 '13 at 04:59

paxdiablo · Accepted Answer · 2013-01-30T06:32:45.563

5

The ideal use case for recursion is when you reduce the "search space" massively on each recursion level. For example, consider a binary search where each recursion level halves the remaining search space.

Your particular problem is that you're trying to do 8000 levels of recursion since each level simply decrements the value. That's going to require a fairly large chunk of stack space.

You can look into increasing the stack size for your JVM with the -ss or -oss options (depending on implementation, of course). But that will only buy you so much.

In terms of timing the whole recursive operation, I would simply store the time before the top-level call in main(), then compare that to the time after that top-level call returns, something like:

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

There's no need to try and do it within the recursive call itself.

If you want to do it at certain points within the recursive call, you can initialise a "global" counter variable (one outside the recursion itself, such as a class-level static variable) to 0 and have the recursive function increment it for every recursion level.

Then have it output the time deltas at the points you're interested in, such as when the variable is set to 10, 100, 1000 and so on.

edited Jan 30 '13 at 06:32

answered Jan 30 '13 at 04:37

paxdiablo

854,327
234
1,573
1,953

Just curious, is it correct to teach beginners to write factorial using recursion? – Alvin Wong Jan 30 '13 at 04:42
2

It's fine to teach the _concept_ of recursion, it's just not something I'd do in production code. Factorial is another of those slowly-reducing-search-space problems. However, with factorial, at least you're likely to overflow your integers before you overflow your stack :-) Recursion is an elegant tool but, like real tools (hammers and such), you have to properly target the job. Nobody wants to have to cut down a Karri tree with a Phillips-head screwdriver. – paxdiablo Jan 30 '13 at 04:45
1

I'm not sure which is worse. I'd rather overflow the stack and be notified of the problem. 1+ for a great discussion! – Hovercraft Full Of Eels Jan 30 '13 at 04:46
@paxdiablo If only there were languages with TCO .. =^_^= – Jan 30 '13 at 04:48
1

@pst: "TCO"? Please elaborate. :) – Hovercraft Full Of Eels Jan 30 '13 at 04:49
I realize that it is doing it 8,000 times, but it's what the professor wants. This is for Discrete Structures, and I'd much rather not use Recursion, but he wants us to experiment and return to him as to why they are different. The algorithm he wanted us to solve is "1*2 + 2*3 + 3*4 + ...n(n+1) so that's why it's only decrementing by 1 each time. Also, I tried doing the timer but won't it only output that timer once? I want it like the Non-Recursion and do it at 10, 100, 1000, etc. – Nick Jan 30 '13 at 05:00
@Nick, that's okay, you should do what the prof wants, then possibly ignore such stuff when you hit he real world :-) The use of the options I listed should allow you you to increase the stack capacity. In terms of timing parts of a recursive operation, I've added a solution for that as well. – paxdiablo Jan 30 '13 at 06:34

score 0 · Answer 2 · edited May 23 '17 at 10:31

Try increasing the stack size.

As for measuring time

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

StackOverflowError using Recursion

2 Answers2