Recursion explained with the help from Inception

People love to joke about recursion. As the saying goes:

“In order to understand recursion, one must first understand recursion.”

You will see recursion mentioned in Twitter threads and Reddit comments. If you search for recursion on Google, they even joke about it by adding a "Did you mean: recursion" at the top of the search results.

Even though these are funny they don't really explain recursion very well or why we use it.

At its simplest level, recursion is a function that calls itself, but there is more to it than that.

The point of recursion isn't just to call itself over and over again in an infinite loop. If you do that you will just end up with a stack overflow exception.

Recursion is more like the film Inception.

Here is a quick recap if you haven't watched Inception before or don't remember much. Don't worry I won't spoil it for you if you haven't watched it yet.

Dom Cobb aka Leonardo DiCaprio, makes his living doing corporate espionage. Instead of spying he steals the information from people's subconscious while they are dreaming. In the film, a guy called Saito hires Cobb and offers him the chance to wipe his criminal record clean, if he can implant the idea of dissolving a company in the mind of one of his competitors.

To be able to implant an idea into the subconscious, it isn't good enough to go into one dream he has to go several layers deep. So a dream, inside a dream, inside a dream.

In order to wake someone up from the dream they need to receive a kick, a sudden jolt that will wake them up. This has to be done at each level so they can wake up from each of their dreams.

They also have to be mindful of not going too deep otherwise they will enter what they call limbo, a dream realm where anything is possible and you can experience a year in the space of 4 minutes in the real world.

So where am I going with all this?

Well, a recursive function is like a dream, it can call itself in the same way that you can enter a dream inside a dream.

In your recursive function, you will always have an exit condition which is like the kick that wakes you up and takes you back to the calling function.

Without this kick, you will keep going into deeper and deeper levels of recursion and eventually enter limbo, which in our case is met with a stack overflow exception.

If you still have lots of questions about recursion, like the final scene in Inception, then let's have a look at where we can use it.

Where Recursion is Used?

Recursive functions are mostly used for navigating tree-like structures like the folder structure on your computer.

Each folder can contain other folders, which contain more folders but eventually, you will get to a folder that just contains files. Then you have to navigate your way back up the folder structure to get where you started.

The same structure can be seen in the comment threads on YouTube videos or blog posts.

I will be very disappointed if no one starts a recursion thread in the comments, so please leave a comment down below.

Any place that has an unknown number of nested elements can use recursion to navigate through them. For example, I have used recursion for parsing logical expressions that contain brackets that contain more expressions that also have to be parsed.

A common example of recursion is calculating the Fibonacci sequence. The sequence starts with 0 and 1 and then each following number is calculated by adding up the previous 2 numbers.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

So, let's say we want to calculate the 10th number in the Fibonacci sequence. We can use a recursive function like this one:

    public int Fib(int n) {
        if (n <= 1)
           return n;

        return Fib(n - 1) + Fib(n - 2);
    }

In this case, n starts from 0 so we need to put in 9 to get the 10th number in the sequence.

To work out the 10th number we need to add up the previous 2 numbers. But we don't know what they are, so we need to call the function again, twice in order to work them out.

This happens again and again until we get to either a 0 or a 1, where we finally return a number and the result works its way back up the call stack until we get our final result of 34.

Recursive functions are useful and you get nice simple code but they aren't the most efficient way of doing things. For each call we have to push and pop methods from the call stack which results in poor performance.

In the Fibonacci code, we also end up calling the function with the same number multiple times which isn't very efficient. In this case, you would get better performance from a loop, especially at high numbers.

As with all things in programming, it is important to pick the right tool for the job and now that you understand recursion that is one more tool you can use.

📨 Are you looking to level up your skills in the tech industry?

My weekly newsletter is written for engineers like you, providing you with the tools you need to excel in your career. Join here for free →