HOW A RECUSION WORKS – STACK FRAMES

When a program calls a subroutine – the current module suspends processing and the called subroutine takes over control of the program. When the subroutine completes its processing and returns to the module that called it, the module wakes up and continues its processing. One important point in this interaction is that, unless changed through call by reference, all local data in the calling module are unchanged. Every local variable must be in the same state when processing resumes as it was in when processing suspended. Similarly, the parameter list must not be changed. The value of the parameters must be the same before and after a call, unless they are reference parameters.

Let’s look at an example of a simple call and see how it works. Figure 3 contains an algorithm called testPower that prints the value of a number x raised to a power y. To illustrate the function call, we use a separate algorithm, power, to determine the actual value of x^y.

Our little program contains three local variables: the base number, base; the exponent, exp; and the answer, result. The base and exponent values must not be changed by the call to power. When power terminates, it returns the value of x^y , which is stored in the local variable, result.