CSCI.1200 - Computer Science II
Summer, 2002
Worksheet 17
;''Recursion

Reading: Deitel & Deitel 3.12 - 3.14

The Run-Time Stack

Stacks are used in a number of applications, but one of the most basic is the Run-Time Stack, also known as the Call Stack or the Program Stack. When a program is running, whenever a call to a function is encountered, the system stops executing statements in the current function and starts to execute statements in the newly called function. Whenever a function terminates (either with a return statement or because execution reaches the last statement of the function), the next statement executed is the statement after the function call in the calling function. The data structure that manages this is a stack. The element type of the stack is called a stack frame and contains, among other things, the memory area for parameters and local variables and the return address (the address where program execution will continue when the current function finishes).

Consider this program fragment:

   6  void FctnOne()
   7  {
   8      FctnTwo();
   9  }
  10
  11  void FctnTwo()
  12  {
  13      // Show stack here
  14      ...
  15  }
  16
  17  int main()
  18  {
  19      FctnOne();
  20      ...
  21  }

During the execution of this program, at the time that the Show stack here statement is executed, the run-time stack would look like this.

FctnTwo, (returning to FctnOne line 9)
FctnOne, (returning to main line 20)
main

When a function is called, it is pushed onto the top of the run-time stack. The function at the top of the run-time stack is actively running. In the above example, FctnOne cannot continue until FctnTwo is finished. Similarly, main cannot continue until FctnOne is finished. Whenever the active function terminates, it is popped off the top of the stack. Thus, functions finish in the reverse order in which they are called.

In using the debugger in Microsoft Visual Studio, you should have become familiar with the Context pop-up menu in the Variables window of the debugger. This window shows you each of the functions in the run-time stack at the point where the debugger paused execution of your program. It is very useful in cases when your program crashes during a call to a library function (e.g., strcpy), and you want to see what line in your program made the function call that crashed.

The Visual Studio debugger has another window called Call Stack that shows you not only the sequence of function calls, but also the line number each function is stopped at. You can bring up this window by clicking with the right mouse button on an empty spot in the program Menu Bar, and selecting Call Stack from the menu that pops up.

Recursion

The run-time stack lets us see how the computer keeps track of things when functions call other functions. This mechanism also allows a function to call itself. This process known as recursion. Here is a simple example:

     1	#include <iostream>
     2	using namespace std;
     3	void fctn(int);
     4	int main()
     5	{
     6	   fctn(4);
     7	   cout << endl;
     8	   return 0;
     9	}
    10	
    11	void fctn(int n)
    12	{
    13	   if (n > 0) {
    14	      cout << n << " ";
    15	      fctn(n-1);
    16	      cout << n << " ";
    17	   }
    18	}

In this example, main makes a call to fctn at line 6. Line 7 of main will not be executed until the function call has been run to its completion. That call, fctn (n = 4), will run to line 15, where it makes another function call -- which happens to be a call to itself. The call to fctn (n = 4) must wait until the call to fctn (n = 3) finishes. It is as though a fresh copy of the function is being executed. The value of the parameter n for the second call (3) is stored in the run-time stack separately from the place where its value is stored for the first call (4). If you drew out the statements being executed thus far, it would look like this:

int main ()
{
  fctn(4); -----> fctn(n = 4)
                  {
[main is waiting]   if (n > 0) {
                      cout << n << " ";
                      fctn(n-1);        -----> fctn(n = 3)
                                               {
                  [fctn(4) is waiting]           if (n > 0) { [next statement to execute]

This function will end up calling itself three more times, until finally the call to fctn (n = 1) ends up calling fctn (n = 0). For that call, you see that the test of the if in line 12 fails, so no further function calls are made. When this call to fctn(0) finishes, the call to fctn(1) can finally continue. Similarly, this call will then finish and return control to the call to fctn(2), as drawn below:

int main ()
{
  fctn(4); -----> fctn(n = 4)
                  {
[main is waiting]   if (n > 0) {
                      cout << n << " ";
                      fctn(n-1);        -----> fctn(n = 3)
                                               {
                  [fctn(4) is waiting]           if (n > 0) {
                                                   cout << n << " ";
                                                   fctn(n-1);        -----> fctn(n = 2)
                                                                            {
                                               [fctn(3) is waiting]           if (n > 0) {
                                                                                cout << n << " ";
                                                                                fctn(n-1);        <--- just finished
                                                                                cout << n << " "; [next statement]

The remaining recursive calls finish similarly, with control ultimately returning to main, line 6.

Exercise 1: What does this program print? (The solution is at the end of the worksheet.)

One of the reasons recursion is a difficult concept to understand is that there can be multiple instances of the same variable. In the above example, there were as many as five instances of the variable n -- one for each of the recursive calls to fctn. Early programming languages like Fortran and Cobol allowed only one instance of each variable, and so recursive calls were not permitted, but modern languages like Java and C++ support multiple instances of a variable. If a function has a local variable x, but during a particular run of a program that function was never called, then x would never be instantiated; i.e., memory to store x would never be allocated. (For example, a function which handles errors when reading a file never gets called if the program is run with a file that has no errors, so its local variables are never given space in memory.) On the other hand, if at a particular instant during the run time of the program there were four calls to this function, then there would be four instances of x, each with its own memory and its own value.

Exercise 2: Trace the contents of the run-time stack as the above program is executed. Show the contents of the run-time stack each time a stack frame is pushed or popped, i.e., whenever a function is called or finishes execution. For each stack frame, show the name of the function, the value of any local variables, and the return address, i.e., the line number of the next statement to be executed for that function. (The solution is at the end of the worksheet.)

Writing recursive functions

All recursive functions consist of two main parts:

• A base case which can be solved directly, within the function.
• A recursive case which is solved by making use of a recursive function call for which the problem is reduced in some way.

In the example above, the recursive case is within the body of the if statement, and the base case does nothing but exit the function. The recursive function call reduces the problem by reducing the value of n by 1.

Most recursive functions will contain an if statement to check if the base case has been reached. If that has happened, the function call finishes without making any more recursive calls. If the base case has not been reached, the function will process some small portion of the problem and pass the remainder of it to a recursive call.

If these two parts are not well-constructed, the recursive function may not terminate properly because it continues to call itself without ever hitting a base case. This is similar to the infinite loops that can occur with iteration, such as a while loop whose boolean condition never becomes false. There is a significant difference, however, in that an iterative loop might not be chewing up memory and would run ``forever'' (really, until interrupted by the user or system administrator). A recursive function, on the other hand, is using more memory for a new stack frame each time it recurses, so the eventual result is stack overflow--however much space was initially available for the run-time stack, it quickly becomes exhausted and the operating system must terminate the program. (We still refer to this situation as ``infinite recursion'' since it theoretically would run forever if we had infinite memory.)

Students often find it difficult to ``think recursively,'' i.e., to write recursive solutions to problems. It takes practice. Some problems are naturally recursive; i.e., the solution is much easier to write using a recursive algorithm than using a non-recursive algorithm. Other problems can be solved equally well using iteration (looping) or recursion.

Here is a somewhat more involved example of using recursion. Pascal's triangle represents the binomial coefficients in the expansion of $(x+1)^n$. It is typically drawn like this:

                          Column k=0  1   2   3 etc.
Row n=0                          1   /   /   /
      1                       1     1   /   /          
      2                    1     2     1   /
      3                 1     3     3     1
      4              1     4     6     4     1
      5           1     5     10   10     5     1
      6        1     6    15    20    15     6     1
      7      1    7    21    35    35    21     7     1
      etc.

How can we write a function int pascal(int n, int k) that gives us the coefficient for any position in the triangle?

First, we must notice that any given coefficient has a relationship to the elements above it in the triangle. Specifically, each number is the sum of the two numbers directly above it. Written as a formula, we have $C_{n,k} = C_{n-1,k-1} + C_{n-1,k}$ where $n$ is the row and $k$ is the column. For example, $C_{5,2}$ is the item in row 5, column 2 (like good computer scientists, we start counting at zero), and it has the value 10, which is the sum of the value in the fourth row, first column ($C_{4,1}$ which is 4) plus the value in the fourth row, second column ($C_{4,2}$ which is 6).

This formula will be used in our recursive case, because we are able to compute the answer to $C_{n,k}$ based on the answers for smaller coefficients. In C++ code, we can express this recursive case like so:

    int answer = pascal(n - 1, k - 1) + pascal(n - 1, k);

This statement will work if we successfully write the pascal function, which we are still in the middle of writing. The trick is to ignore the fact that we haven't finished it yet.

How do we come up with the base case, then? How should the recursion know when to stop? The triangle gets narrower as we head towards the top of it. Whenever we reach the end of a row or column, the value there is 1. So how do we know if a given call to our function is this base case? If we have reached the left edge of the triangle, then $n$ can be any value, but $k$ is zero. If we have reached the right edge, then $n$ and $k$ are the same value.

In code, it looks like this:

    if (k == 0 || k == n)
       int answer = 1;

Now we have both the recursive case and the base case. Let's put the function together.

  int pascal (int n, int k) {
     int answer;
     if (k == 0 || k == n)
        answer = 1;
     else
        answer = pascal(n - 1, k - 1) + pascal(n - 1, k);
     return answer;
  }

Is this function guaranteed to reach the base case eventually? Every recursive call reduces n by one, so as long as n is positive to begin with, it will eventually reach the base case. (On the other hand, the second of the two recursive calls does not reduce k, so we cannot say that k will eventually reach zero.) What happens in our function if n or k is negative, or if k is larger than n? The triangle doesn't cover these possibilities, but our recursive function has to check for them, or else we will be stuck with infinite recursion and stack overflow. This test must be added to the function to make it complete and correct.

Even with the additional tests, the resulting function is a short and elegant solution to the problem, since it exactly mimics the mathematical definition of the binomial coefficients making up Pascal's triangle. But is it efficient? (The answer is discussed below.)

Exercise 3: The greatest common divisor of two integers x and y is the largest integer that evenly divides both x and y. The gcd of x and y can be computed efficiently as follows: if y is equal to 0, then the gcd of x and y is x; otherwise the gcd of x and y is the same as the gcd of y and the remainder of x divided by y. (This is known as Euclid's algorithm. It is believed to be one of the first algorithms ever written down.)

For example, to find the gcd of $x=20$ and $y=12$, since $y \neq 0$, we divide 12 into 20, and discard the result to get the remainder 8. Now we want the gcd of $x=12$ and $y=8$. Since $y \neq 0$, we divide 8 into 12 to get the remainder 4. Now we want the gcd of $x=8$ and $y=4$. Since $y \neq 0$, we divide 4 into 8 to get the remainder 0. Now we want the gcd of $x=4$ and $y=0$. Since $y=0$, the gcd is 4.

Write a recursive C++ function that implements this algorithm for int parameters x and y.

Recursion is sometimes used to do something which can be done as well or better using iteration (i.e., looping).

Exercise 4: Write an iterative C++ function that computes the gcd. Which do you think is more efficient (in terms of speed), your recursive gcd function or your iterative one? Which uses more space?

Once you get the hang of recursion, a recursive solution can be easier to write down and understand than an iterative one. But recursive functions can be much less efficient than iterative ones, in terms of both time and space usage. This is true, for example, of the recursive pascal function given above for computing binomial coefficients.

For the gcd example, the computing times of both your iterative and recursive solutions should both be $O(N)$ where $N = \mbox{max}(x, y)$, making both algorithms practical for large $N$ from the standpoint of time used. But the recursive solution uses space (for the run-time stack) that is $O(N)$ in the worst case, and thus stack overflow will occur when $N$ is large enough. The iterative version needs only a constant amount of space.

Thus, in both of these cases, an iterative solution is to be preferred over a recursive solution. Are there then any cases where recursion has an advantage? The answer is (no surprise) yes. One important case is when you are working with tree structures, as will be discussed in the next worksheet. Often the easiest way to write an algorithm for searching or modifying a tree structure is recursively, and such algorithms can be just as efficient or more so than corresponding iterative algorithms.

When working with linear sequences, such as arrays or linked lists, recursive algorithms are generally less efficient than iterative ones, in terms of time and especially in term of space. Nevertheless, as a warm up for working with tree structures, and to introduce the idea of auxiliary functions, let's look at some examples of recursion applied to linked lists.

For example, you could use recursion to print a linked list. Here is the code to do this: a member function void PrintList() with no arguments that prints the entire list, and another member function void AuxPrintList(node<T> *current) that prints all nodes starting from a given node, current. The latter function is called an auxiliary function for the recursion. The primary function simply calls the auxiliary function with head as its argument. The auxiliary function checks to see if its argument is NULL. A NULL argument means that we are at the end of the list, so we do nothing. Otherwise, we print out the value of the data field and call the auxiliary function again, passing in the next field as the argument.

void LinkedList::PrintList()
{
    AuxPrintList(head);
    cout << endl;
}

void LinkedList::AuxPrintList(node<T> *current)
{
    if (current != NULL) {
         cout << current->data << ' ';
         AuxPrintList(current->next);
    }
}

Exercise 4: Copy the file /dept/cs/cs2/download/linkedlist2.cpp This contains some code for a linked list class. Add three additional member functions to it.

int listsize()

which returns the number of elements in the list.

void printlist()

which prints out each element in the list, one element per line (given to you above).

void printdoublelist()

which prints the elements in the list and then prints the list backwards. For example, if a list of students contained three elements, Mickey Mouse, Donald Duck, and Snow White, a call to this function would print:
Mickey Mouse
Donald Duck
Snow White
Snow White
Donald Duck
Mickey Mouse

Your new functions must use recursion rather than iteration.

Hint: For each of the three functions, you will need a second auxiliary function which takes one more argument, a node, and this is the function that calls itself recursively.

#include<iostream.h>

template <class T>
class node {
 public:
     T data;
     node<T> * next;
     node(){next=NULL;}
     node(T item){data=item;next=NULL;}
};
 
template <class T>
class linkedlist
{
 private:
    node<T> *head;
 public:
    linkedlist(){head=NULL;}
    void insertathead(T item) {
         node<T> *temp = new node<T>(item);
         temp->next = head;
         head = temp;
    }
};

int main()
{
    linkedlist<int> listofints;
    int i;
    for (i=0;i<5;i++)
        listofints.insertathead(i);
    cout << listofints.listsize() << endl;  // 5
    listofints.printlist();  // 4 3 2 1 0
    listofints.printdoublelist(); // 4 3 2 1 0 0 1 2 3 4
    return 0;
}

Exercise 5: Write a main program that creates a linked list of $N$ integers (1 through $N$, say) and calls listsize to verify its length. Try running it with larger and larger values of $N$ (say, 1K, 2K, 4K, 8K, ...) until you find some value $M$ that causes stack overflow to occur. Recode listsize iteratively and test it with larger values than $M$ to show that they succeed.

Solution to Exercise 1:
4 3 2 1 1 2 3 4

Solution to Exercise 2: