Understanding Recursion

What is Recursion: Please Bear with me

This is going to be a short and technical article so please bear with my bad English and writing style. Language is also a mean of communication and sometimes it fails to convey understanding so I will brain dump the concept in plain English to the best of my ability.

Simple but Confusing

Recursion is indeed a confusing topic (especially for students)  though it is simple. Simple concepts are not necessarily easy to implement because it depends to what extent the concept directly follow natural way of thinking. I believe the main reason why recursion is confusing is that it does not follow direct natural way of thinking as the case in iteration. I will provide an example to demonstrate the concept of recursion and hopefully it will help readers master the skill of thinking recursively but before jumping to the topic right a way let us roughly define what a function means from a programming perspective.

A Function is a Function

In procedural languages like C or Pascal, source code is composed from functions or procedures. On the other hand object oriented languages like C++ do have functions (called methods) but they are embedded inside class definitions. Regardless of implementation details (Recursion, Iteration, Complexity, Performance, etc) a function is nothing but a block of code that receives zero or more parameters and return some sort of output. For example the following function receives two integer parameters A and B and returns the sum of the two integers.

Calling this function is straight forward. You simply provide the required input and receive the expected output. In case of recursive functions it is no different at all you just call a function with the appropriate input and receive some expected output so what makes it different and confusing.

Recursive Functions

A recursive function has to be invoked for the first time from outside function definition however it keeps calling itself from inside function definition until it reaches a stopping condition. From computer’s perspective if a function calls itself or calls another function it is still a regular function call as long as you invoke the right function name and specify the required input parameters.

Divide and Conquer

I know I still did not explain the confusing part, why would even bother calling the function from within its definition in the first place. Recursion follows a well known algorithm design technique called divide and conquer which means breaking a problem into sub problems of the same or related type until the sub problem become simple enough to be solved directly. The solutions to the sub problems are then combined to give a solution to the original problem. So how divide and conquer relates to a function calling itself, in the first call to the recursive function you provide the input with full size, the moment the function starts invoking itself it should provide a smaller size input, you keep providing a smaller size in each call until the input is simple enough to solve. The final step is combining all solutions into a single grand solution.

Example

I admit I am still talking abstractly. The words are still dry so let us try to understand recursion using an example while thinking loudly. The factorial example is great but I guess it sounds boring to encounter this example in every article that talks about recursion. I am going to discuss an example that is easier to solve using iteration however we will solve it using recursion to improve our skills in thinking recursively.

Consider this example. Given an array of integers find the maximum number in the array. This problem can be solved iteratively by looping through the array element by element and comparing the current element to the current maximum while updating the maximum as long as the current element is larger. This is the natural way of thinking, you assume the first element to be the maximum then check every single item in the array to see if it is larger or not. Thinking recursively does not follow such a natural way but it is a little bit different. Do you still recall the divide and conquer technique if so then that is recursion in one way or another. Let us apply divide and conquer to this problem.

One way to do that is to break the array into two halves then find the maximum of the first half then the maximum of the second half then return the larger maximum (since we have two maximums). The first call to the recursive function operates on the whole array then subsequent calls operate on halves of the array and so on till the point we operate on a single item. Consider the following array of integers

We start with one array of 10 elements then two arrays of 5 elements, then 4 arrays of 2 or 3 elements, then 8 arrays of one or two elements. As you can see once the array is reduced to an array of one or two elements it is very easy to find the maximum number. If the array has only one element then the maximum is the element itself. If the array consists from two elements then the maximum is the larger element. Take a look at the figure below starting from the bottom of the left branch of the tree:

Then from the bottom of the right branch of the tree:

And finally we take the larger maximum of the left and right branches

Based on the example above let us try to characterize the general anatomy of a recursive function.

1. We need a base case for input so that the function stops calling itself beyond that point. In our example the base case is when the array has only one element in that case you just return the element itself as the maximum.
2. The second issue that we need to pay attention to is that the input or problem size must be reduced every time the function calls itself. In our example we start with full array then with half array until we provide an array consisting of a single element. If input size is not reduced then the base case will not be reached which causes the recursive function to overflow stack memory.
3. Solutions should be combined to produce the final solution. In our example the maximum in the left side of the recursion tree was 7 while the maximum on the right side of the recursion tree was 10. We compare those two numbers and return the larger one.

Understanding Recursion C++

Let us apply the rules above and come out with a recursive C++ function:

As you can see we just implemented the three rules mentioned earlier. Please note the following:

1. I and J represent start and end array indexes. The first time you call the recursive function you provide I = 0 and J = length of the array
2. Once you calculate the position of the middle element then the start index I = 0 and J = m for the left branch while I = m + 1 and J = length of the array for the right branch. This is how we reduce the input size by playing with the values of I and J
3. When I == J this means we are pointing to a single element which is the base case
4. Once the left max and right max are calculated we combine the two solutions by returning the larger one

So here is the deal. If you want to improve your recursion skills then you need to practice more on those rules. Before ending this article let me be clear about the following

1. Recursion does not exactly mean divide and conquer. It is the other way round, divide and conquer is an algorithm design technique that uses recursion
2. Divide and conquer can be used to design fast algorithms such as binary search and merge sort. In our example we did not improve performance simply because we operated on both branches of the tree. Comparing this to binary search, in every call to the recursive function we operate on one branch of the tree

So please keep that in mind as the main purpose of this article is to understand the concept of recursion not how to design fast algorithms. I hope this article is helpful but I am sure there is nothing like practice. Just search this blog for Recursion for more examples. Please use the comments section below for questions, corrections or feedback. Thanks for reading.