CIT 594 Idioms for Recursion
Spring 2011, David Matuszek

It seems that a number of students are still having trouble with recursion. Maybe this page will help.

The four rules

I've given four rules for doing recursion in class. They are:

  1. Handle the base case(s) first.
  2. Recur only with a simpler case.
  3. Do not both read and modify external variables. (It's best to use only parameters and local variables.)
  4. Don't look down. (That is, think about only one level of the recursion, and get that one right.)

When to use recursion

There are a lot of times you can use recursion. However, whenever you are dealing with a recursively defined data structure, you probably should use recursion. Think about how the data structure is defined; that tells you where the recursion should be. (Note: Examples are pseudocode, and have not been tested.)

Definition Idiom Examples
A linked list is a node containing:
  • A value, and
  • A reference to a linked list.
Do something with the head (first element) of the list, and recur with the tail (rest of the list).

int add(List L) {
    if (L == null) return 0;
    else return L.value + add(L.next);
}

void printList(List L) {
    if (L == null) return;
    print (L.value);
    printList(L.next);
}

A binary tree is a node containing:

  • A value,
  • A left subtree, and
  • A right subtree

where the "subtrees" are themselves binary trees.

Preorder: (1) Do something with the root, (2) recur with the left subtree, (3) recur with the right subtree.

Inorder: (1) Recur with the left subtree, (2) do something with the root, (3) recur with the right subtree.

Postorder: (1) Recur with the left subtree, (2) recur with the right subtree, (3) do something with the root.

int add(BinaryTree B) {
    if (B == null) return 0;
    return B.value + add(B.leftChild)
                  + add(B.rightChild);
}

void inorderPrint(BinaryTree B) {
    if (B == null) return;
    inorderPrint(B.leftChild);
    print (B.value);
    inorderPrint(B.rightChild);
}

A tree is a node containing:

  • A value, and
  • One or more subtrees.

Preorder: (1) Do something with the root, and (2) recur with each child.

Postorder: (1) Recur with each child, and (2) do something with the root.

int add(Tree T) {
    if (T == null) return 0;
    int sum = T.value;
    for (Tree child : T.children) {
        sum += add(child);
    }
    return sum;
}

void printTree(Tree T, String indent) {
    if (T == null) return;
    print (indent + T.value);
    for (Tree child : T.children) {
        printTree(T.child, indent + "   ");
    }
}

Parsing a string

In the current assignment you are supposed to parse a list of words into a tree. But a list of words doesn't have a recursive structure--at least, it doesn't have the same kind of recursive as a tree.

Or does it?

For simplicity, I am going to ignore blocks for a while. I am also going to ignore strings that result in a sequence of trees. For example, the string "while less-than? x 100 set x times x 2" is fine--it gives a single tree--but "set x 1 set y 2" is two separate trees. That can wait.

Look at it this way. The input string is a list of functions. Some of the words are zero-argument functions, like y and 2, but they are all functions. So, what is the structure of a (legal) input string? It consists of (1) the name of a function with arity N, and (2) N functions that are arguments. So function #1 is the root of the tree, and its children are the N following functions. The list of words does have a tree structure; it's just hidden, and you have to bring it out.

In pseudocode:

Tree parse1(WordList WL) {
    get the next word W from the WordList WL;
    create a tree T with root value W;  // base case
    for i from 1 to arity(W) {
        C = parse1(WL);                 // recursion
        add C as a new child of T;
    }
    return T;
}

I called this method parse1 because it parses and returns one tree.

Brackets, [], are a special case. You can think of the open bracket, [, as a function named [] whose arguments are everything up to the next closing bracket, ]. So you don't know ahead of time how many arguments [ is going to have, but you just keep getting subtrees until one of them is ]. At that point you don't, of course, add the ] as a subtree; you're just done finding the arguments to this function.

Oh wait...what if there are brackets nested inside your brackets?! You're going to have to count how many brackets deep you are, and...and... Relax. That isn't thinking recursively, it's looking down. So what if your brackets contain brackets? That's just another function. You don't have to count anything, just let the recursion take care of it. Trust to the recursion.

Finally, your input is going to be a string that represents a sequence of functions--one after the other, just like a block. And you can handle it just like a block. Instead of beginning with a [, begin with the beginning of the string; and instead of ending with ], end with the end of the string.

Façade functions

Often you will find that you want to call a function with certain parameters, but the function is most easily written with different, possibly more, parameters. In this case you can write a façade function that has the parameters you would like to call it with, and that function simply calls another function (often with the same name) that has parameters that are easier to work with.

For example, suppose you want to print a tree as an indented list. This is easy to do if you include the indentation as an argument (see the pseudocode above), but there's no reason to make the user include this argument. Solution: Write a function that doesn't have the argument, and all that it does is call another version of the function with an initial value for that argument.

As another example, suppose you want to parse a string, but the parse is most easily done if the method is given an iterator over a list of strings (the individual words in the original string). Here's what to do: Write a façade function that takes a string as an argument, breaks it into a list of words, and calls a second function with an iterator over that list to do the actual work.