The Hex, The Curse and The Recurse

From the get-go, we are taught to think iteratively. For example to find the sum of the numbers from 1 to 5 you would immediately add 1 to 2, then add that result to 3, then add that result to 4 and then to 5.  (1 + 2 + 3 + 4 + 5 = 15)

There is another way to solve the problem however, and its called recursion. The concept of recursion has always been rather difficult to grasp. To illustrate, lets apply recursive thinking to the summation problem above. Instead of summing successively from 1 through to 5, we attack the problem from the other end as it were. In other words, we express the sum to N as N + sum(N-1), or in our case 5 + (sum to 4). The sum to 4 is itself broken into 4 + (sum to 3) and so on.  By repeatedly breaking down the problem in this way, we arrive at the sum to 1 which is of course, 1. We then add up the results of each sum. 

This solution might seem counterintuitive and you may well ask why use recursion at all when there are more seemingly straightforward ways to solve a problem. The method works well with data structures like decision trees that are characterized by repetition, or for problems that can naturally be broken into sub-problems. 

If a problem is simple enough, rather solve the problem directly and return the solution. Otherwise split the problem up into smaller problems each with the same structure as the original. Then solve each of those smaller problems, combine the results to get the overall solution and return the overall answer.

The notion of a bigger problem being broken down into smaller parts that can be easily tackled is known as divide-and-conquer. In our example, the sum to 1 which is intuitively simple to grasp, is known as the base case. All recursive algorithms must have a base case to terminate.

Implementing recursive algorithms on large data sets can gobble up memory and the recursive method can be slow to execute. There are a few methods to overcome this. For example, the results of expensive functions can be stored for later use when they occur again. So when writing iterative code starts to get complex, think about using recursion. Repetition as they say, creates mastery.