Recursion is the process of solving a problem in terms of smaller versions of the same problem. Since the problem gets smaller each time, the process eventually terminates in a problem (the “base case”) that can be solved directly. Be sure of three things:
- The problem gets smaller each time.
- You include a solution for the base case.
- Each case is handled correctly.
That’s really all there is to it.
But what about visualizing how the code runs? You don’t have to. And that’s the point: sometimes a recursive solution is easier precisely because you don’t have to understand in detail how it executes. Graham explains in his Lisp book why tracing the code execution is unnecessary if not harmful.
Students learning about recursion are sometimes encouraged to trace all the invocations of a recursive function on a piece of paper. … This exercise could be misleading: a programmer defining a recursive function usually does not think explicitly about the sequence of invocations that results from calling it. … How do you visualize all those invocations? You don’t have to.