Last year in school, one of my assignments was to explain the reasons for using recursion. I realized I forgot to share this, so here is a slightly edited version of that assignment.

When should you consider using recursive algorithms when writing a program?

The answer to this question is really simple. But first, it’s important to know why we use recursion in the first place.

When you first learn about recursion, it may be hard to believe this, but it’s greatest benefit is to make complicated algorithms easier to write, and be read by humans.

Why Recursion is Good.

So the main reason we use recursion is to simplify (not optimize) an algorithm into terms easily understood by most people. A classic example is the binary search.

The algorithm for binary search in plain English:

1. 1. Start with a sorted collection of data (like a telephone book).
   2. Find the middle of the collection.
   3. Ask, is this the item I’m searching for?
      • If yes, done!
      • If no… Ask is the item before or after the middle item?
        • If before… Then find the middle of the first half
        • If after… Then find the middle of the second half
   4. Then repeat step 3 and so on until the item is found, or else the item is not present in the collection.

The most important key phrase in those steps is “and so on”. It’s a big give away that recursion might simplify a problem. The problem can be simplified by calling the binary search algorithm on simplified versions of the problem. What if step 3 looked like this?

3. Ask, is this the item I’m searching for?

• • • If yes, done!
    • If no… Ask is the item before or after the middle item?
      • If before… Binary Search the first half
      • If after… Binary Search the second half

Here we have an example of defining an algorithm with the algorithm itself – recursion! Now the reason that this works, is that there is a base case. The base case is the most simple problem that can be solved without using recursion. In this example that’s the condition that the item is found. There is one more base case in the recursive binary search – and that’s the case that the list is empty. If the list is empty, we don’t need to do anything, just stop the algorithm. Here are the two versions in code.

Iterative Binary Search:

 

Notice even in the iterative implementation we still have a base case to end the while loop – that is if mid is found. But we don’t need to check if the list is empty, because if it is then hi will not be >= to low – it will be less.

In the case that the list is empty, or we didn’t find the number we’re looking for we return -1.

As you’ll see in the recursive version of this algorithm, we need to check for that base case first before we do any recursive calls or else we will run into infinite recursion resulting in a StackOverflowException.

Another difference is that our actual parameters include the hi, and lo values. This is because each time we call binary search we are only interested in searching the new, smaller half of the collection, hence from the lowest possible location to the highest possible location.

Recursive Binary Search:

 

You might find that the above example makes more intuitive sense. The code spells out the way you’d define binary search if explaining it in English. Whereas the code in the iterative example is a little more complicated to spell out in normal speak.

This is the main reason why we choose to use recursion. The binary search algorithm isn’t the best example of showing this since the iterative version isn’t too complex anyways. However, because both versions are simple it tends to be easy to explain – hence why it’s used in most textbooks and tutorials.

Other algorithms that you may have seen from textbooks are the Tower of Hanoi problem and the Quicksort. Both are examples of problems that are difficult to solve iteratively but incredibly intuitive to solve recursively.

Why Not Use Recursion?

The reason recursion can be bad is that it can be incredibly inefficient. The example of binary search is an example of the most efficient case for a recursive method. That’s because when the base case is met, and a value is returned to the previous method in the recursion stack, no new recursive calls are made. In other words each method in the recursion stack is only called once. Here’s a diagram to show the flow of a recursive binary search:

As long as the condition needed for the base case is false, there will be a new call to the binary search method until a base case is met. Then the result is returned all the way out of the recursion until it gets to the original caller, and execution continues on.

In other algorithms such as the Fibonacci sequence, recursion is more complex and the diagram looks more like a tree – a recursion tree. Here’s another diagram that I found to show this:

 

Each node in this tree represents a method call in the recursion tree. You should take note of how many times fib(1) is called. You can see that many values are being calculated more than once which makes this algorithm very inefficient. In fact, the extra calculations increase exponentially as n increases.

Try implementing your own Fibonacci function with recursion and pass it a value of 45 to see what happens.

Now, this might make recursion seem bad, but know that an algorithm like Quicksort uses recursion and it has a best case of O(n log n), meaning even with very, very large data sets it still performs better than any other sort algorithm most of the time. There are cases where Quicksort is O(n²), but it’s so rare it’s not considered a problem – and to go off on a tangent, there are guards to protect against this case, but they reduce the average case.

So the simple answer is that if you have a large problem that makes more intuitive sense to think about recursively rather than iteratively than it’s a good idea to use recursion, so long as the cost in performance doesn’t hinder your application.

---

So that was my answer to the question, “when should you use recursion?” about a year ago. I do agree with pretty much everything said above, but I’d like to add another point.

Recursion is also a major part of functional programming. It’s how you achieve loops without state. A traditional (or imperetive) loop will usually look like this in any C inspired language (excuse me while I switch to JavaScript):

for (var i = 0; i < 5; ++i) {
 console.log(i);
}

Notice the assignment, var i = 0. This is setting the state of i and then with each iteration the state is changing.

The problem with state is explained really well by Robert C. Martin (Uncle Bob):

To summarize: as CPU core counts increase, concurrency is going to be the defacto way of getting better performance out of applications we write. A major problem with managing state, is that we, humans, suck at it.

State, makes writing concurrent code basically impossible. Which is one of the reasons there is this movement toward functional programming now that hardware has allowed it to be a practical and effective paradigm.

To write a loop without changing state, you could do something like this:

loop (n) => {
 if (n === 0) {
  return 0;
 } 
 loop(n-1);
 console.log(n);
}

In a real functional langauge this would be more terse, but what’s happening there, is we are still counting just like the for loop before. Only we are never manipulating state. Notice that the value of n never changes – instead, we are passing a new value to each call of loop().

Each execution context is a new value of n. Thus, we’ve avoided state, and n can be an immutable property just like if this were algebra and not programming.

It was interesting for me to pull up an old peice from school and seeing how my perspectives have changed a year later. Hopefully this article helped you out too 🙂

If you liked this, don’t forget to share, and leave a comment below!

Cheers,

Dan