title: Recursive Fibonacci memoization
body: <p>I need some help with a program I'm writing for my Programming II class at universtiy. The question asks that one calculates the Fibonacci sequence using recursion. One must store the calculated Fibonacci numbers in an array to stop unnecessary repeated calculations and to cut down to the calculation time.</p>
  <p>I managed to get the program working without the array and memorization, now I'm trying to implement that and I'm stuck. I'm not sure how to structure it. I've Googled and skimmed through some books but haven't found much to help me solve how to implement a solution.</p>
  <pre><code>import javax.swing.JOptionPane;
  public class question2
  {
  static int count = 0;
  static int [] dictionary;
  
  public static void main(String[] args)
  {
  
  int answer;
  int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog(&quot;Enter n:&quot;));
  
  javax.swing.JOptionPane.showMessageDialog(null, 
          &quot;About to calculate fibonacci(&quot; + num + &quot;)&quot;);
  
  //giving the array &quot;n&quot; elements
  dictionary= new int [num];
  
  if (dictionary.length&gt;=0)
  dictionary[0]= 0;
  
  if (dictionary.length&gt;=1)
  dictionary[0]= 0;
  dictionary[1]= 1;
  
  
  //method call
  answer = fibonacci(num);
  
  //output
  JOptionPane.showMessageDialog(null,&quot;Fibonacci(&quot;+num+&quot;) is &quot;+answer+&quot; (took &quot;+count+&quot; calls)&quot;);
  }
  
  
  
    static int fibonacci(int n)
    {
  count++;
  
  // Only defined for n &gt;= 0
  if (n &lt; 0) {
    System.out.println(&quot;ERROR: fibonacci sequence not defined for negative numbers.&quot;);
    System.exit(1);
  }
  
  // Base cases: f(0) is 0, f(1) is 1
  // Other cases: f(n) = f(n-1) + f(n-2)/
  if (n == 0) 
  {
    return dictionary[0];
  }
  
  else if (n == 1) 
  {
    return dictionary[1];
  }
  
  else
  return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);
    
   
  
  }
  
  }
  </code></pre>
  <p>The above is incorrect, the end of my fib method is the main problem. I've no idea how to get it to add the numbers recursively to the correctly parts of the array.</p>