title: Java Memoization Recursive Method
body: <p>Been trying to figure out this issue for a while but can't get my head around it. </p>
  
  <p>Question: Given the method below. Optimise it with memoization.</p>
  
  <pre><code>public static long cat(int n) {
      if (n == 0)
          return 1;
      long result = 0;
      for (int i = 0; i &lt; n; i++) {
          result += cat(i) * cat(n - i - 1);
      }
      return result;
  }
  </code></pre>
  
  <p>What I have tried:</p>
  
  <pre><code>private static int memCat(int n, int[] cache) {
      if (n == 0) {
          return 1;
      }
  
      int result = 0;
  
      if (cache[n] == 0) {
          for (int i = 0; i &lt; n; i++) {
              result += memCat(i, cache) * memCat(n - i - 1, cache);
          }
          cache[n] = result;
      }
  
      return result;
  }
  </code></pre>
  
  <p>My idea behind this is that as the result for all the counts in the inner for loop will be saved. So it does not have to be repeated. </p>
  
  <pre><code>public static void main(String[] args) {
      System.out.println(cat(5)); //Prints 42
      System.out.println(memCat(5, new int[5 + 1])); //Prints 1 
  }
  </code></pre>
  
  <p>My eyes and brain are tired so it may just be a simple mistake.</p>