title: Java Memoization of Recursive method
body: <p>I am trying to create a memoized version of Factorial function. When I call factMemoized(4), it computes the factorial of 4 for the first time and stores it in a Map. When I call factMemoized(4) again, it now gives the stored result instead of recomputing it again. This works as expected. But, when I call factMemoized(3), it recomputes the value, eventhough it had computed fact(3) as part of computing fact(4). Is there any way to make sure that even the values computed as part of recursive calls will be stored in the map without adding the memoization function within the fact() function?</p>
  
  <pre><code>import java.util.HashMap;
  import java.util.Map;
  
  
  public class MemoizeBetter {
  
  public static &lt;F, T&gt; Function&lt;F, T&gt; memoize(final Function&lt;F, T&gt; inputFunction) {
      return new Function&lt;F, T&gt;() {
        // Holds previous results
        Map&lt;F, T&gt; memoization = new HashMap&lt;F, T&gt;();
  
        @Override
        public T apply(final F input) {
          // Check for previous results
          if (!memoization.containsKey(input)) {
            // None exists, so compute and store a new one
  
            memoization.put(input, inputFunction.apply(input));
          }else{
              System.out.println("Cache hit:"+input);
          }
  
          // At this point a result is guaranteed in the memoization
          return memoization.get(input);
        }
      };
    }
  
  public static void main(String args[]){
  
  
  final Function&lt;Integer, Integer&gt; fact = new Function&lt;Integer, Integer&gt;() {
        @Override
        public Integer apply(final Integer input) {
          System.out.println("Fact: " + input);
          if(input == 1)
              return 1;
          else return input * apply(input -1);
  
        }
      };
  
      final Function&lt;Integer, Integer&gt; factMemoized = MemoizeBetter.memoize(fact);
  
      System.out.println("Result:"+ factMemoized.apply(1));
      System.out.println("Result:"+factMemoized.apply(2));
      System.out.println("Result:"+factMemoized.apply(3));
      System.out.println("Result:"+factMemoized.apply(2));
      System.out.println("Result:"+factMemoized.apply(4));
      System.out.println("Result:"+factMemoized.apply(1));    }    
  }
  
  interface Function&lt;F,T&gt;{
      T apply(F input);
  }
  </code></pre>