Let me show you a real life example of what recursion is and how it works.
The Python 🐍 problem-solving bootcamp is starting soon. Join the second cohort now!
Recently I tweeted a thread that explained recursion. In case you missed it, I included it here 👇
I have gotten multiple requests to explain recursion.— Rodrigo 🐍📝 (@mathsppblog) April 24, 2022
Let me explain recursion with an example 👇
But that was mostly a joke. In this article, I'll try to explain recursion with a real life example.
Let's go 🚀
When people think of recursion, people think of functions that call themselves. After all, recursion is about self-reference. Something that is recursive is something that depends on itself. Therefore, a recursive function will call itself.
But how? And why?
Recursion is useful in certain types of problems. Recursion is mostly useful when:
But what kind of problem looks like that?
The other day, I had to look for a receipt for something I had purchased. I didn't remember the address of the store and I needed to go there again. So, I took my stack of receipts and started looking for it... But the stack was big and I was in a hurry! So, what did I do?
The other half, I kept for myself and started looking for the receipt there. But I was in a hurry! So, what did I do?
The other half, I kept for myself, and started looking for the receipt there. But I was in a hurry! So, what did I do?
Can you guess what I did? I split the stack in half again and asked someone else to help me. Then, I took the stack I kept for myself and I looked for the receipt in there.
And this is the key idea!
I started the example with this sentence:
“So, I took my stack of receipts and started looking for it...”
And just now, after asking for help a couple of times, I wrote this:
“Then, I took the stack I kept for myself and I looked for the receipt in there.”
But these look like the same task, don't they? So, why did I ask for help? Was it even worth it? Yes it was!
Because now I have a much smaller stack to look through! So, I have a subproblem (a smaller problem) that looks pretty much like the original problem.
Task: find a specific receipt in a stack of receipts.
Notice how the 3rd bullet point of the strategy matches the task. So, this is a big part of recursion. If a problem you have can be split into smaller problems, and the smaller problems still look like the original... That's a good candidate for recursion. The part where you split the problem into smaller ones is the recursive part.
Because it's when you start with one problem: Look for a receipt in a stack of receipts. And you create multiple problems: Look for a receipt in the two stacks of receipts.
The other ingredient missing tells you when to stop splitting the stack in half. In the world of recursion, we call it the base case. Say I had plenty of family members around and I kept splitting the stack in half. I split, and split, and split, and suddenly I look at my stack: it's a single receipt. Well, that's easy to handle, right? I don't need to split the stack in half again... I barely even have a stack, it's just a single receipt! I just look at the receipt and check if it's the one I'm looking for. If it is, good. I found it! If it's not, I'll wait for my family members to report back to me.
Is this making any sense? Can you see what I'm getting at? Let's take this receipt example and translate it to Python 🐍.
My function takes a stack of receipts (a list of receipts) and another receipt and looks for it. Here it is, with lots of comments:
# Write a function that looks for a receipt. # Returns True if it finds it, False otherwise. def find_receipt(stack_of_receipts, receipt): # Do we have a stack so small, we can do everything by ourselves? if len(stack_of_receipts) == 1: # The stack really is small! # Is this the receipt we are looking for? return stack_of_receipts == receipt # The stack is big, so we really need help. their_stack_half = stack_of_receipts[:len(stack_of_receipts) // 2] # First half my_stack_half = stack_of_receipts[len(stack_of_receipts) // 2:] # Second half # Ask a family member to look for the receipt in their stack. they_found = find_receipt(their_stack_half, receipt) # Look for the receipt in my half: i_found = find_receipt(my_stack_half, receipt) # Did any of us find the receipt? return they_found or i_found
Does this function work? Well, we can try it out...
>>> receipts = ["supermarket", "book 1", "book 2", "Python course", "pizza"] >>> find_receipt(receipts, "something else") False >>> find_receipt(receipts, "book 2") True >>> find_receipt(receipts, "supermarket") True >>> find_receipt(receipts, "pizza") True
And it does seem like it is working! Here you go, a recursive function that we built together! I really like to think that the recursive part is asking someone for help. Does that analogy make sense to you?
This was a tiny toy example of recursion. There are many other things to be said about recursion, but I hope this gave you an overview of the concept.
If a problem can be split into subproblems and the subproblems are similar to the original problem... Then recursion might be appropriate!
I write about Python every week. Join +16.000 others who are taking their Python 🐍 skills to the next level 🚀, one email at a time.