Demystifying Recursion

At first glance, recursion is very confusion. Two things about recursion makes it confusing:

• How can we call a subroutine that's still being defined?
• How about the local variables and parameters? How can a subroutine track different parameters? More specifically, how can a parameter of a subroutine track different values?

Here are the answers:

• A recursive subroutine only looks being defined from your perspective (as you are creating the subroutine). To the compiler, the entire subroutine is already defined by the time the program is compiled.
• There are two different aspects to a subroutine. The first is its definition. This is a static description of how the subroutine should behave. This is analogous to the definition of a word in a dictionary. The second aspect to a subroutine is the run-time environment that provides storage for local variables and parameters.

  There is only one description of how the subroutine should perform operations. However, there is one environment to store the values of parameters and local variables for each invocation of the subroutine. This means each invocation can track its own parameters and variables.

  An environment in this context is a call frame. Recall that a new call frame is allocated and created for each invocation of any subroutine. This is how Pascal (and most other modern programming languages) can isolate the parameters and local variables of one invocation from another.

Calling recursively is really no different from calling in general. Instead of getting puzzled by the apparent mystery of recursion, one way to deal with recursion is to forget it is recursion! Just remember what the subroutine is supposed to do and what it requires to know (parameters) when you are ready to call it from anywhere. This approach (of focusing on what and not how when you invoke a subroutine) usually helps.