University of Toronto
Department of Computer Science
csc 148: Introduction to Computer Science

Online Homework: Recursion

Tracing a Recursive Method

Recursion occurs when a subprogram calls itself, either directly or indirectly. At first, it can seem a little weird to see a subprogram calling itself. Most people find it all makes sense once they understand how the calls and returns really work, and this is best seen by very carefully tracing the code. Assume that we have written the following simple class for creating nodes in a "binary tree" -- a tree in which each node can have up to two children:


class TreeNode {
     int num;                // The actual data in the node
     TreeNode left, right;   // For referring to the node's children
}

Now consider a recursive function that returns the maximum value in an entire tree. The code appears in the applet below.

Assuming that the tree below has already been built we will now trace a call to maxVal with the root of the tree (node-5) as its actual parameter.

To see the code run from start to finish, click on "go". You can change the speed of tracing using the "slower" and "faster" buttons. To stop the trace, click "stop".

What you are going to see in the trace

The large frame on the left shows the method call that we are currently tracing, the values of the local parameters, the code itself (with the line currently executing highlighted), and the value to be returned by this call.

Every time the method calls itself, a new frame is pushed on top of the old one; and every time a call returns, its frame is popped off the stack of frames.

You may need to widen your browser's window to see the picture on the right. It shows the tree upon which the method is operating. Node colours mean the following:

blue: we have not been to this node yet
You can make the trace start again after stopping, but the tree ought to be redrawn in blue to show that no nodes have been visited yet. It's not -- one more thing on my to-do list.
yellow: we are working from this node now
red: we have put this node on hold while we deal with one of its children
green: we are completely done with this node

Note that null child nodes are not shown, so the picture won't change when we go visit, for example, the left child of the node with the 1 in it.

Testing Your Understanding

Now try tracing a recursive method yourself, on paper. Here's the method:

// Prints all of the integers in the tree referred to by `root' in "inorder"
// order, and with children displayed to the right of their parents.  The
// entire tree is indented `numSpaces' spaces.
// Preconditions: root must have a value (although it may be null)
// 		numSpaces must have a value >= 0.

void printTree (TreeNode root, int numSpaces) {

    // If there is nothing in the tree, do nothing at all.
    if(root != null) {
        // But if there is something in the tree, print out the entire left
        // subtree indented 3 more spaces to the right, then the root's own 
        // value indented `numspaces', and finally print out the entire right 
        // subtree indented 3 more spaces to the right.
        printTree (root.right, numSpaces + 3);
        printSpaces(numSpaces);
        System.out.println (root.num);
        printTree (root.left, numSpaces + 3);
    }

}

Again assume that the tree shown above has been built, and that a variable called "r" refers to the root node. Trace the following call:


     printTree (r, 0);

Question A.

What would happen if the original call printTree passed a reference to some node other than the root?

Question B.

This is a pencil and paper question, so go grab a piece of paper and something to write with. Draw a small binary tree with 5 nodes, and trace a call to the following recursive function, assuming that a reference to the root of your tree is passed in:

int sumTree (TreeNode root) {
    if(root != null) {
        return root.num + sumTree(root.left) + sumTree(root.right);
    }
}

Question C.

What would happen if the recursive line in the function were:

        return root.num + sumTree(root.right) + sumTree(root.left);

Writing a Recursive Method

Now that you understand the mechanics of recursion, you should be ready to write your own recursive code. Let's write a recursive function that returns the number of leaves in a binary tree. We will tackle the problem by answering a series of nine simple questions. You can use these nine steps whenever you write a recursive method.

Try to solve each question before looking at its answer.

1. What information must the subprogram know to do the job, and what must it tell back?

2. Write a subprogram header through which all of this information can be communicated

3. Write a comment that explains exactly what it will do, in terms of the parameters.

4. When is the answer so simple that we know it without recursing?

5. Write an if-statement for the degenerate case(s).

6. Describe the answer in the recursive case(s) in terms of the answer on smaller inputs.

7. Simplify if possible.

8. Put it all together.

9. Last but not least, trace it!

Get out a piece of paper and trace the code by hand to see if it behaves as you wish.

Testing Your Understanding

Question D. What would happen if we took out the degenerate case for handling a tree with just one node -- case (2) above?

When to use Recursion?

One philosophy is that recursion should be used all the time. It is possible to write programs that never use loops! In fact, "functional" programming languages such as Lisp are designed to support this philosophy. The advantages of this approach? Purity: one simple and elegant control structure (recursion) can do it all. And recursive is often easier to reason about -- to argue (and if desired, to prove) that it is correct.

But even if one doesn't take this extreme approach, there are problems which nothing but recursion can solve elegantly. We may have discussed one such problem in lecture: tree traversal. If one is going to "traverse" a tree, that is, go through the tree and visit every node, something must be done to keep track of where one has been and where one has yet to go. But because a tree is not a linear structure, one can't use a single reference to keep track of this. There are only two solutions: keep a stack of nodes that must be revisited, or use recursion. The first solution is quite tedious to implement because one must build and keep track of the stack oneself. The recursive solution, on the other hand, is extremely short and elegant. See the lecture slides for actual code.

The printTree method, which you traced above, is another example of code that cannot be solved elegantly without recursion.

Which of the following operations can only be done elegantly with recursion?

A. Search in a linked list.

B. Search in a sorted linked list.

C. Search in a binary tree.

D. Search in a binary search tree.

E. Printing a tree.

F. Printing a binary search tree.