When I was first reading up on recursive solutions to algorithms, I kept hearing about space complexity and the call stack, and at first had no idea what was up. It's turns out, it's actually pretty simple! I'm hoping this post can condense into one spot what was a disparate learning experience for me.
Let's define some things first.
What is recursion? Honestly that one is worth a blog post (or a few) in itself, so if you're not already familiar with how recursion works, I recommend you read this excellent rundown or find something similar to help you understand, as I'm not going to be going into it fully here. I'll wait.
You back? Okay cool. Next, what is Space Complexity?
Space complexity in algorithm development is a metric for how much storage space the algorithm needs in relation to its inputs. -Technopedia
So if my solution to an algorithm involves creating two hash-tables, my space complexity is going to be a lot higher than if it only involves creating a single primitive variable.
Finally, what is the Call Stack?
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. - Wikipedia
Translation, it's how many tasks the system is juggling at once.
With recursion, every time you call the function recursively you add one more function to the call stack. Until you hit the 'bottom' and start traveling back up or out, you're adding one each time. Now suppose that your function requires establishing a variable. That variable is being established anew every time you call the function.
It goes like this. You have a function that requires that 2 rocks be balanced in your hands. Every time you call the function, you add two more rocks to your pile. You can't start putting rocks down until the function they are for finishes. Because of the nested nature of recursion, you're doing a lot of things at once, and so that pile is going to grow bigger and bigger and may get pretty unwieldy and heavy.
That pile of rocks is your space complexity! The more levels of recursion you have, the higher it will get. You're going to get better performance out of your machine the fewer functions you've got going.
Recursion is really neat, and can lead to some beautifully simple code, but it definitely has its drawbacks.
Top comments (10)
I'm also from "The Odin Project" and feel like I lost a lot of wind in my sail after hitting recursion. Your analogy really helps with understanding the double edge nature of recursion. Thank you for the quick read!
From the Odin
Son of Odin here as well. Loved your article, especially the analogy provided at the end. Makes recursion really stick.
an Odinite too
From TOP, I love how you simplified your article and not going all too technical on it.
Here's another way to make it more relatable
The Shopping Cart Analogy for Recursion
Imagine you’re at a mall, pushing a shopping cart. As you walk through the aisles, you pick up items one by one and place them in your cart. The first item you pick up goes at the bottom of the cart, the second item goes on top of it, and so on. You know the price of each item individually, but to find out the total cost, you need to go to the checkout counter.
Here’s where the magic of recursion comes in:
First In, Last Out (FILO):
At the checkout counter, the cashier starts by scanning the last item you added to the cart (the one on top). Then they move to the second-to-last item, and so on, until they finally reach the first item you placed in the cart (the one at the bottom).
Breaking It Down:
Each item is like a step in a recursive function. The cashier doesn’t calculate the total all at once—they process one item at a time, adding its price to the running total. This is similar to how a recursive function breaks a problem into smaller, manageable pieces.
The Base Case:
The checkout process ends when the cashier reaches the first item in the cart. In recursion, this is called the base case—the point where the function stops calling itself and starts returning results.
The Total:
Once all the items have been scanned, you get the total cost. In recursion, this is the final result after all the smaller problems have been solved.
Thanks for your analogy. And if you are from the Odin Project, this is my message to tell you that you're doing great and should not give up.
Hello from TOP ^_^
Hola desde TOP. Excelente articulo, ,uy comprensible.
Hello from Odin also and thanks for the excellent explanation
Hello, I'm Odinite too!!
Any article used by Odin Project is doomed to be recognised only for being in Odin Project