Recursion Using Stacks

Function calls and "the stack"

Recursion Example

Consider the following program using a recursive function:

#include <iostream>
using namespace std;

int f(int n) {
  int k, r;
  if (n == 0) return 0; // 0
  k = n*n;              // 1
  r =                   // 2
    f(n - 1);           // 3
  return k + r;         // 4
}

int main() {
  // Get Input
  int x, y;
  cout << "Enter value x: ";
  cin >> x;

  // Call f
  y = f(x);

  // Print results
  cout << y << endl;
  return 0;
}

Can you figure out what's being computed here? At any rate, here's what goes on inside the computer when this function is called:

Recursive calls to f get pushed onto the stack of active function calls resulting in many copies of the function f, each with different argument and local variable values, and at different lines in the function. That's what the computer is doing with recursion. In fact, all the computer really needs to remember for each active function call is the values of arguments and local variables and the location of the next statement to be executed when control gets back to the function. So, really, "the stack" looks a little more like this:

When you look at it this way, you should notice that element of "the stack" is an object that wraps up several pieces of data ... which we can do in our programs with classes. In other words, in our program, we can make our own stack and simulate recursive functions for ourselves, rather than leaving it to the computer and the compiler.

Translating Recursion to Iteration

Any recursive function can be translated into an iterative function using a stack - we simply use a stack in our program to model what "the stack" in the computer would be doing with our recursive function. Let's do this for the recursive function example from the previous section.

First we need to make a class for f's activation records, since that's what we'll store on the stack. From the above picture, we see exactly what data needs to be stored in this class: f's argument, local variables and the location of the next line to be executed.

class f_record {
public:
  int n;    // f's argument
  int line; // current line in f
  int k, r; // local variables
  f_record(int arg):n(arg),line(0) { }
};

We'll keep a stack of activation records for calls to f. To make a call like f(5), we'd create an f_record with n set at 5, and push it on the stack:

Stack<f_record> S;
f_record call(5);
S.push(call);

Then we go into a loop which keeps up as long as there are activation records on the stack. At each iteration of this loop we simulate the execution of the next line of the activation record on top of the stack. When the activation record on top of the stack comes to its return line, we'll have a variable for it to store the returned result in. So assuming that what we want is to simulate y = f(x), without the recursion, here's what we do:

  // Initialize recursive function simulation:
  // Returned result will be stored in retval
  int retval;
  Stack<f_record> S;   // stack of active calls
  S.push(f_record(x)); // call f(x)

  // While there's an active function call left
  while(!S.isEmpty()) {
    f_record curr = S.pop();
    int LINE = curr.line++;

    if (LINE == 0) {
      if (curr.n == 0)
        retval = 0;
      else
        S.push(curr);
    }
    else if (LINE == 1) {
      curr.k = curr.n*curr.n;
      S.push(curr);
    }
    else if (LINE == 2) {
      f_record recurse(curr.n - 1);
      S.push(curr);
      S.push(recurse);
    }
    else if (LINE == 3) {
      curr.r = retval;
      S.push(curr);
    }
    else if (LINE == 4)
      retval = curr.k + curr.r;
  }
  y = retval;

int f(int n) {
  int k, r;
  if (n == 0) return 0; // 0
  k = n*n;              // 1
  r =                   // 2
    f(n - 1);           // 3
  return k + r;         // 4
}

This is a fair bit of code compared to our original function, but the code is pretty easy to come up with. After all, we just have a separate case for each line of the function f. Each individual case is pretty straightforward. The thing to keep in mind here is that any recursive function can be translated to an iterative segment of code using a stack. The procedure for doing it is pretty much what we did with our example.

An ending note concerning "the stack"

Each program has its own stack of active function calls. It differs from what we did in our recursion-to-iteration example above in that instead of having multiple copies of the same function on the stack, it may have many different functions. This doesn't change much. What it does change is that each activation record must include a tag indicating what function it belongs to.

The stack of function calls for a program usually has fixed size. If the program makes too many function calls, the stack runs out of room and the program crashes. This is referred to as "stack overflow". In practice, you've got enough space on the stack that this won't happen unless you have an infinite recursion (i.e. you forget a base case), or you do something recursively in a very silly way. (For example: if you create a linked list of several million elements and call a recursive function for computing the list's length, you'll probably get yourself in trouble!)