title: Java recursion method StackOverflowError with Integer object
body: <p>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.</p>
  
  <p>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. </p>
  
  <p>My code is:</p>
  
  <pre><code>private static int smartestFib(Integer goalNum)
  {   
      if (goalNum &lt; 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);
      }
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>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? </p>
  
  <pre><code>private static int smarterFib(int goalNum)
  {
      assert (goalNum &gt;= 0): "The variable goalNum may not negative.";
  
      if (goalNum &lt; 2)
          return 1;
      else
      {
          ArrayList&lt;Integer&gt; sequenceList = new ArrayList&lt;Integer&gt;(Arrays.asList(new Integer[] {1,1}));
          return smarterFib(goalNum-2, sequenceList);
      }
  }
  
      private static int smarterFib(int goalNum, ArrayList&lt;Integer&gt; priorValues) 
  {
      assert (goalNum &gt;= 0): "The variable goalNum may not negative.";
      assert (priorValues != null): "The array priorValues has not been initialized.";
  
      if (goalNum &lt;= 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);
      }
  }
  </code></pre>
  
  <p>I can't see why this one doesn't cause a problem and my new one does..</p>