Recursion explained with the help from Inception

Recursion explained with the help from Inception

by | 4 min read
Published:
Updated:

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.

🚀 Are you looking to level up your engineering career?

You might like my free weekly newsletter, The Curious Engineer, where I give career advice and tackle complex engineering topics.

📨 Don't miss out on this week's issue

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.

Inception Dream Sequence

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.

Fibonacci Tree

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.

Repeated Calls

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.


🙏 Was this helpful? If you want to say thanks, I love coffee ☕️ , any support is appreciated.


ALSO ON ALEXHYETT.COM

SOLID Principles: Do You Really Understand Them?

SOLID Principles: Do You Really Understand Them?

  • 16 June 2023
SOLID Principles are one of those things that every developer has heard of but few fully understand. If you use an object-oriented language…
Python List Comprehension: With Examples

Python List Comprehension: With Examples

  • 20 February 2023
Working with arrays can be a bit of a pain in most languages. If you want to make changes to an array you need to use a FOR loop, a bit like…
Finally Understand Regular Expressions: Regex isn't as hard as it looks

Finally Understand Regular Expressions: Regex isn't as hard as it looks

  • 10 January 2023
There’s nothing like a regular expression to strike fear in the heart of a developer. Regular expressions (regex) are used for a lot of…
How I would learn to code (if I could start over)

How I would learn to code (if I could start over)

  • 06 January 2023
When I was 8 years old I learnt how to code. I learnt to code from an old BASIC book that my Dad had lying around from his ZX Spectrum. I…
Understanding Big-O Notation

Understanding Big-O Notation

  • 03 January 2023
It’s important when you’re writing applications especially, those that are going to be processing a large amount of data that you understand…
Stack vs Heap Memory - What are the differences?

Stack vs Heap Memory - What are the differences?

  • 30 November 2022
In modern programming languages such as C# or Java, we tend to take memory management for granted. Gone are the days when we need to call…
Git Flow vs GitHub Flow

Git Flow vs GitHub Flow

  • 10 November 2022
Losing code that you have spent hours writing can be painful, which is why we use version control (or source control) to store our code and…
Bitwise Operators and WHY we use them

Bitwise Operators and WHY we use them

  • 26 October 2022
Bitwise operators are one of those concepts that a lot of programmers don’t understand. These are not used a great deal anymore so you can…