Once and For All, What Is Recursion??? (No Fibonacci/Factorial)

Photo by Sebastian Herrmann on Unsplash

When I started learning how to code, as most developers to be, I encountered the term “recursion”. It was hard for me to put my head around it and every time I tried to google more about it I kept on seeing the Fibonacci or factorial of n examples over and over again. It frustrated me because it didn’t help me see the full potential of recursion or to understand other use cases.

Why should we bother?

Recursion is a good technique to implement when we have a solution to a sub-problem that could help us solve a bigger problem in a clean way. If you are interviewing to a technical role you should probably get yourself familiar with the concept, as it’s being asked often. Personally, I feel like I only fully understood the concept of iteration after figuring out recursion.

Photo by JESHOOTS.COM on Unsplash

When shouldn’t we use recursion?

It’s usually not the most optimal solution as it can create a stack overflow, and simply takes a lot of memory to generate many calls in the call stack. Most often a simple loop could be more efficient.

Today I’ll try to walk you through the process I went through myself to understand how recursion really works, and when can we use it.

Definition

By definition, recursion is a function that calls itself until it doesn’t. That’s it. Now, what does it mean?

“a function that calls itself”

It means that this problem as a whole is actually solvable by performing the same action on the entire problem, and smaller parts of it. So, we are expecting to have multiple levels/iterations where we actually want to perform the same actions, and they are all wrapped in one function that we call for each level/iteration (every time with different arguments).

“until it doesn’t”

We will set base cases that will define when we should spot drilling down/up/iterate.

Base Cases

Just like in a while loop in JS/Python we have to specify a terminating condition. If we won’t do that, we would get into an infinite loop. Ouch!

These terminating conditions are called base cases.

Here is an example for a base case:

We want to solve the “eat letters” problem, that is, to take a word as an argument to our function, print the word and remove the last letter, and repeat until the word only consist of one letter. So the base case (stopping condition) will be that the word has actually no letters. Why? Because we don’t want to continue iterating and removing letters that don’t exist in the word. We also don’t need to continue, because when we are out of letters to cut, it means we’ve finished the task.

# print the whole word and then remove the last element every time# Pizza
# Pizz
# Piz
# Pi
# P
def eat_letters(word):
if len(word) < 1:
return

print(word)
return eat_letters(word[:-1])

Look at the example above, we have 3 things happening in the function:

  1. Base case check — we check if we should handle this case with the current argument. If not, we return and we will stop iterating.
  2. Function core — we handle the argument and execute the core job of the function. Here it’s very simple, the function should just print the word.
  3. Iteration — we continue iterating with a modified argument. We modify the argument the recursive function takes, just like in a while loop. So, every time the function is called it’s called with a shorter word, until it doesn’t.

Conceptually, we will see recursion in action in problems that have different levels. For example, let’s think of the following problem:

We have a Russian Babushka doll (or “Matryoshka”) and we are so eagerly curious whether there is something else inside the smallest one. So, how would we solve it? We can open them, one by one, and check. So the same solution would apply for all the levels.

Photo by Simon Hurry on Unsplash

In code:

simple_babushka = {
'babushka': {
'babushka': {
'babushka': None
}
}
}

awesome_babushka = {
'babushka': {
'babushka': {
'babushka': 'gift 🎁'
}
}
}


def which_babushka(doll):
content = doll.get('babushka')
if isinstance(content, dict):
return which_babushka(content)

# last doll
if content is None:
return 'not a fun babushka'
else:
return 'yayy, awesome babushka! 🎁'

print(which_babushka(awesome_babushka))

What happens under the hood

Photo by Derzulya Zaza on Unsplash

Unlike in a loop (for/while/etc.) when we are using recursion to iterate over some concept, we build a call stack. It means that every time we call the function again, the previous function call stays “open” and the new function call is added on top of it, so the previous function waits for those on top of it to finish before it can close. Practically, that happens only when we stop iterating (in the base case).

So in our example, the lowest call in the stack is the one that takes the entire word (‘Pizza’) and the one on top is with an empty string as an argument. When this function will return (thanks to our base case) the rest of the calls could then also be cleaned from the stack.

Let’s have another example! Now, we will focus on how we use recursion when we want to iterate over something that is not by levels. Let’s imagine we try to bake a wonderful french bread, without a recipe (I know 🤯). We like automating stuff so we created a function that will help us know when the dough is ready to bake. We don’t have the exact quantities so we’re just rolling it, adding some flour and water, iteratively. Whenever the function detects that the dough is too dry or too wet, it calls itself again (with the current state of flour and water) and stops when the two are balanced.

Feel free to copy-paste it to your terminal/IDE and play around with it!

def prepare_dough(flour, water):
print(f'iterating with flour = {flour} and water = {water}')
# base case
if
flour == water:
print('dough is ready and balanced')
return
# dough is too try
if
flour > water:
return prepare_dough(flour, water+1)
# the only option left, dough is too wet
else
:
return prepare_dough(flour+1, water)

prepare_dough(5, 1)

In the terminal we would get:

iterating with flour = 5 and water = 1
iterating with flour = 5 and water = 2
iterating with flour = 5 and water = 3
iterating with flour = 5 and water = 4
iterating with flour = 5 and water = 5
dough is ready and balanced with 5 water and flour

Conclusion

I hope this article helped you maybe understand this topic a bit better. I know I struggled only seeing examples of fibonacci and factorial, and I figured writing up my explanation wouldn’t hurt. I hope I managed to pass the message through, that recursion is just a fancy, clean way of iterating, nothing more to it.

If you liked this, follow me for more similar articles!

Full Stack Software Developer. Love learning new things and now also write about them! 💪🏻

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store