Whenever possible, you should build up a cache dynamically (approaching the desired answer step by step) instead of using recursion, which typically has no answer until it reaches the terminal state and thereby has to propagate all the way down and then propagate back up