Understanding Recursion: Part 1/4

Remember the initial days when you were forced to learn recursive programming? And how you were thankful that it’s all over and you don’t have to deal with the whole thing anymore? Well, why do you think that is? Recursion is not all that bad! A lot of beginners who start out with programming somehow end up hating recursion. The main reason is that people don’t really understand how to deconstruct a given problem to make it suitable for recursion. Recursive code, by itself, is nice and small. But understanding what exactly is the recursive part can be pretty confusing. If used correctly, recursion can be one of the best weapons in your programming arsenal. Let’s see what’s beneath all this!  

What exactly does recursion mean?

Recursion is actually a process of repeating something in a self-similar way. It is very commonly used in programming. It is a way of thinking about problems such that we can break them down to our advantage. To give a real life example, if you place two mirrors parallel to each other, the images you see in those mirrors are reflections of each other. Since the images are reflected back and forth without any end, it forms an infinite recursion. Programming, on the other hand, uses the finite version of recursion.

How is it relevant in programming?

In programming, we have something called “functions”. A function is a block which carries out a specific task. For example, there can be a block which adds sums up the squares of three numbers. So anytime you want to do that, just give the three numbers as inputs to this function and it will give the corresponding output. Pretty simple stuff! Some of the functions, if defined the right way, can be made recursive.

A function can be recursive if it can call itself. As in, when you are defining a function, you use the function itself to build it. Let’s consider a real life example. Let’s say you have defined a method to travel from San Francisco to New York City in a car. There are many things to be considered like fuel, travel time, fatigue, food, etc. You have to consider everything and design a method to achieve this task. This method will take two cities as inputs, and it will tell you what to do. But inside this method, you will define a very simple rule to get from San Francisco to Las Vegas (which is on the way to New York City, but much closer to San Francisco) and then say that you will use the same bigger method to get from Las Vegas to New York City. The advantage of defining the bigger method this way is that you can give any two cities as input and it will work just fine. So in reality, you actually just defined a very simple rule to solve a very simple problem (getting from San Francisco to Las Vegas). You are now using this rule to extend it to a much bigger problem.

An alternative to all the jibber-jabber

We can continue talking about recursion using programming terminology, but looking at some simple code is a much better way to get a hang of recursion. To start off, let’s look at a small piece of code. Here’s an example of a simple recursive function:

void printNumber(int k) 
{
    if (k == 0) 
        return;
    cout << k << endl;
    printNumber(k-1);
    cout << "and we are done" << endl;
}

The above function prints all the numbers starting from ‘k’ to 1. As you can see here, the function printNumber() is being called inside itself. Let’s say you call the function with the input argument ‘3’, here’s what happens inside:

printNumber(3): Since k is not 0, it goes to the next line and prints ‘3’. It will then call printNumber(2) (k-1 = 3-1 = 2). The current status of the code is stored on the stack.

printNumber(2): Since k is not 0, it goes to the next line and prints ‘2’. It will then call printNumber(1) (k-1 = 2-1 = 1). The current status of the code is stored on the stack.

printNumber(1): Since k is not 0, it goes to the next line and prints ‘1’. It will then call printNumber(0) (1-1 = 1-1 = 0). The current status of the code is stored on the stack.

printNumber(0): Since k is 0, it doesn’t go to the next line. It will just return to the previous state on the stack. This is where all the storing on the stack comes in handy! It will go back to those states in the reverse order (last in, first out) and retrieves everything. Once it’s done, it prints the last line i.e. “and we are done”.

Now that we understand the basics of recursion, we will discuss how recursion is used to solve a real programming problem in the next part.

————————————————————————————————-