Java recursion method StackOverflowError with Integer object

Question

I've been trying to make a fibonacci number returner (given an input n returns the element at index position n in the fibonacci sequence). I was trying to make it both recursive and have low space complexity (I don't instantiate any new variables). I use Integer objects as values, and although I am aware their values overflow (they return negative values), this is actually intentional (for education purposes). The function is called smartestFib because it has lower space complexity than my other functions.

The problem arises when I call smartestFib(n) for 130 or higher. It works perfectly fine (with the overflowing considered) for 129 or lower, but it gives exceptions for 130 and up. The main problem is that I can't find out what the exception actually is: It shows so many errors that I can't see the first one, and thus don't know exactly what the error is. Because I don't know the type of the error I can't catch it.

My code is:

private static int smartestFib(Integer goalNum)
{   
    if (goalNum < 2)
        return 1;
    else
        return smartestFib(goalNum-2, 0, 1,1);
}

private static int smartestFib(Integer goalNum, Integer currentNum, Integer lastValue, Integer beforeLastValue) 
{   
    if (goalNum == currentNum)
        return lastValue + beforeLastValue;
    else
    {
        return smartestFib(goalNum, currentNum + 1, lastValue+beforeLastValue,lastValue);
    }
}

I would really appreciate some help on this problem, because the arbitrariness of the problem leads me to believe it is some technical issue I am unaware of, and I have no clue where to look. A lot of thanks in advance.

EDIT: Apparantly it may be a StackOverflowError, thanks a lot! But now I wonder, I have other functions, with higher space complexity, and they are not having this problem. How?

private static int smarterFib(int goalNum)
{
    assert (goalNum >= 0): "The variable goalNum may not negative.";

    if (goalNum < 2)
        return 1;
    else
    {
        ArrayList<Integer> sequenceList = new ArrayList<Integer>(Arrays.asList(new Integer[] {1,1}));
        return smarterFib(goalNum-2, sequenceList);
    }
}

    private static int smarterFib(int goalNum, ArrayList<Integer> priorValues) 
{
    assert (goalNum >= 0): "The variable goalNum may not negative.";
    assert (priorValues != null): "The array priorValues has not been initialized.";

    if (goalNum <= priorValues.size()-2)
        return (priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2));
    else
    {
        priorValues.add(priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2));
        return smarterFib(goalNum, priorValues);
    }
}

I can't see why this one doesn't cause a problem and my new one does..

That's a [StackOverflowError](http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror) — resueman, Dec 02 '16 at 19:38

score 3 · Accepted Answer · edited May 23 '17 at 12:24

Recursion programs work by calling the same method again and gain (i.e., by creating more & more stackframes by the thread calling that method) and after reaching the default stack size, you will get stackoverflowerror.

So to fix the issue, you need to increase the stacksize by passing -Xss as the JVM argument, you can look here.

I have other functions, with higher space complexity, and they are not having this problem. How?

So the difference between 1st and 2nd programs explained below:

The difference is that one uses Boxing (when you use Integer type for goalNum variable) and the other one uses primitive int and when you used the Boxing it is causing the performance issue and the program is failing to complete.

So change your goalNum variable from Integer type to int and then it works (I tested):

private static int smartestFib(int goalNum, int currentNum, 
     int lastValue, int beforeLastValue) {   
         System.out.println(goalNum);
         if (goalNum == currentNum)
             return lastValue + beforeLastValue;
         else {
            return smartestFib(goalNum, 
                   currentNum + 1, lastValue+beforeLastValue,lastValue);
        }
 }

So, to summarize, always avoid unnecessary Boxing/Unboxing (converting from primitives to wrapper types i.e., int to Integer) which becomes more important when you are running extensive computations (like in your recursion). You can look here for understanding more on the subject of how boxing causes performing issues.

Thanks for your comment, this was really helpful! But I was not having this problem for programs that basically did the same thing, and I am completely clueless about where the difference is. Could you have a look at my other code as well? I edited the main post and it would mean a lot to me. — user3500869, Dec 02 '16 at 19:55

score 1 · Answer 2 · answered Dec 02 '16 at 22:06

Stack overflow is not based on the routine's space complexity; it means that you've used on the space on the call stack. Every active function call takes up some stack space, keeping track of values passed in and back, and often context-switching space (register values, etc.).

SmarterFib passes an integer (one word) and an array (one word, by reference; total memory use is N (goalnum) words plus a couple of words overhead). This is a total of 2N words on the stack.

SmartestFib passes four integers for each call, or 4N words on the stack.

I would not normally expect these to have severely different run-time stack requirements: if SmartestFib blows the stack at N=130, I'd expect SmarterFib to blow it well before N=260 (there's some fixed overhead for a call).

Java recursion method StackOverflowError with Integer object

2 Answers2