An optimization over plain recursion when we cache the results of subproblems to reduce time complexity from exponetial to polynomial.