• Dr. Taylor's Page
• Calendar
• Policy
• Resources

Recursion!

Yes, it's back! I know you've seen it before, and that likely, you didn't love it. I distinctly remember being an undergraduate, complaining that learning recursion was a waste of time, because "all of this can just be done easier with iteration." Then I took Data Structures, and discovered I was really wrong.

The simple fact is this: with many, many data structures, recursion is WAY easier to cope with than iteration is. Embrace it, because it's about to make your life easier. Today, then, is an IC210-level reminder of what recursion is, and how it works.

Recursion is a function calling itself. So, if we understand how function calls work, we'll understand recursion a lot better. Imagine the following set of functions (in pseudocode):

f1() {
  print "inside f1"
}

f2() {
  print "starting f2"
  f1()
  print "leaving f2"
}

main() {
  print "starting main"
  f2()
  print "leaving main"
}

If we were to run this program, the output would be:

starting main
starting f2
inside f1
leaving f2
leaving main

To understand why, let's think about the call stack. The call stack works like a stack of plates: plates can only be placed on the top, and can only be removed from the top. For this reason, they're often referred to as LIFO (last-in-first-out). Instead of plates, though, the call stack has the functions that are running; when a function is called, it is placed on the top of the stack. A function ONLY runs when it is at the top of the stack; the rest of the time, it sits and waits for the one above it to return.

So, we start running the program. Obviously, it prints "starting main." At this point, our call stack looks like this:

Our next line is to call the function f2. So, f2 gets put on the top of the stack:

We've done enough programming now to know that now f2 is running, not main. The reason, though, is because now f2 is on the top of the call stack, so main just sits and waits until f2 returns.

So, f2 runs, printing "starting f2." It then calls f1, leading to this stack:

So, f1 runs, and f2 (and main) sits and waits. f1 prints "inside f1," then returns, "popping" off the stack, taking us back to this:

f2, back on the top of the stack, gladly continues where it left off, printing "leaving f2," before returning and popping off the stack itself:

Back on the top of the stack, main now finishes, printing "leaving main," and returning, ending the program.

OK! So, recursion. Let's consider the standard first-recursion-example of finding a factorial using recursion:

int fac(int n) {
  if (n == 0)
    return 1;
  return n * fac(n-1);
}

If fac(3) is run, it runs through happily, until it gets to "fac(n-1)", and which point, fac(2) is placed on top of the stack. fac(2) begins to run, and fac(3) sits and waits for it to return. fac(1) is then placed on top, and fac(2) and fac(3) sit and wait. Finally, briefly, fac(0) is placed on the stack, just long enough to return 1.

At this point, fac(1) picks up where it left off, multiplying its n (1) by what fac(0) returned (also 1), and returning that solution. fac(2) then multiplies that returned value of 1 by its n (2), and returning the solution. fac(3) then multiplies that 2 by its n (3), returning a final answer of 6.

Tips for writing recursive methods

We're going to need a base case (the thing that makes everything stop running; in the above factorial example, it's if n==0), and at least one recursive case. The base case is usually easier... what's an input that makes this problem really easy? Write that first, then make the recursive case build towards it.

Linked List traversal

Here's linked list traversal with iteration:

traverse(Node head) {
  Node tempPtr = head;
  while (tempPtr != null)
    tempPtr = tempPtr.getNext()
}

and here it is with recursion:

traverse(Node head) {
  if (head==null) //Empty lists make this easy, so its a good base case
    return;
  traverse(head.getNext())
}

Make sure you understand how this works. Soon, there will be data structures where the iterative version is pages long, and the recursive version is five lines. You want to know and understand this.

In class, we wrote two other methods, one of which calculated the length of a linked list:

public int length(Node n) {
  if (n == null)
    return 0;
  return 1+length(n.getNext());
}

The other added an element to a sorted linked list. For example, if we have a linked list holding the integers 1, 2, and 4, after running addInOrder(3), we would have a linked list with the integers 1, 2, 3, and 4.

public void addInOrder(int element) {
  first = addInOrder(element, first);
  if (last == null)
    last = first;
}

//This is a helper method, so our user doesn't have to know or care about
//nodes.
private Node addInOrder(int element, Node n) {
  if (n==null)
    return new Node(element);
  if (n.getData() > element) {
    Node t = new Node(element);
    t.setNext(n);
    return t;
  }
  n.setNext( addInOrder( element, n.getNext()));
  return n;
}

Make some examples to try the above on, and understand why it works! Your homework will go better.