The Recursion Checklist

Recursion isn't the hardest principle to understand, but often is not a way of thinking that comes most naturally for developers. Personally, I have struggled with recursion and try as I might to avoid it, sometimes it is the cleanest way! After using it a few times I have become more comfortable with it, and have developed a checklist of what to look for when writing a recursive function.

The Base Case

• Prevents infinite recursion
• Kind of similar to a while loop condition for when to stop looping

The Recursive Call

• Moves towards the base case
• The defined method is called from within itself

Famous Recursion

Words are great, but rarely help you understand a problem... So now let's take a look at a few common examples:

• Fibonnaci
• Trees

Fibonacci

Fibonacci is simply written using recursion but also is incredibly inefficient this way. Nonetheless, consider the following:

  public int fibonacci(int n)  {
     if(n == 0) {
        return 0;
     } else if(n == 1) {
        return 1;
     } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
     }
  }

Fibonacci is a classic algorithm that makes 2 recursive function calls and is exponentially large. Recursion is terminated when n is either 0 or 1. However, although it is most simply written recursively it can be much more efficiently written iteratively, as follows:

  public int fibbonaci(int n) {
     int current = 0; 
     int next = 1; 

     for (int i = 0; i < n; i++) {
        int temp = current + next;
        current = next;
        next = temp;
     }

     return current;
  }

Finding the root of a tree node

Let's assume we are given the following class to represent a node of a tree, and that the values in the tree are populated appropriately:

  public class Node {
     private Node _parent;
     private IList _children;

     public Node getRoot() {
        if (_parent == null) {
           return this;
        }

        return _parent.getRoot()
     }

     public Node getParent() {
        return _parent;
     }
  }

The getRoot method is recursive as it calls itself, and will keep calling itself until it gets to the root node. The root node is where recursion terminates due to the check if the parent is null. As the root node is the value returned in the base case, this value propagates all the way up through the recursive calls to the entry point of the method, and thus this is a simple way to get the root of the tree. Alternatively, this same method can be written without recursion and this may be preferable for the reasons described later:

  public Node getRoot() {
     Node currentNode = this;
     
     while(currentNode.getParent() != null) {
        currentNode = currentNode.getParent();
     }

     return currentNode;
  }

Iteration or Recursion?

When deciding whether to use recursion there are a few things you should consider:

1. How much data are you working with?
2. Is there a simple iterative solution?

How much data are you working with?

This is a very important factor, as if you have too much data and thus very deep recursion, a stack overflow will occur and your program will throw an exception. This is when your program tries to use more space that is available on the call stack. The size of the call stack varies depending on a variety of factors such as machine architecture and programming language.

Some languages, such as Scheme, are optimised to allow for infinite tail recursion, and implement tail call optimisation. Unfortunately, in most languages such as C#, Python and Java, this is not the case. Tail recursion is when the return result comes entirely from the recursive call. For example, our getRoot call is tail recursive as the return result relies entirely on the recursively called function or the base condition. Whereas, the following function is not tail recursion as it relies on the multiplication of the parameter n times the value of the recursive call, and thus the recursive call must be evaluated before the return value can be.

  public int fact(int n) {
     if (n == 0) {
        return 1;
     } else {
        return n * fact(n - 1);
     }
  }

Is there a simple iterative solution?

Often recursion is the simplest way to solve a problem, and this is when it is most commonly used. It is important when choosing whether to use a recursive or iterative approach, to decide whether you can simply implement a solution using an iterative approach. In general, an iterative approach is more efficient as there is less overhead involved.

References

http://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it