DEV Community

Cover image for Recursion and Space Complexity
El Marshall (she/they)
El Marshall (she/they)

Posted on

32 4 3

Recursion and Space Complexity

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.

Image of Datadog

Master Mobile Monitoring for iOS Apps

Monitor your app’s health with real-time insights into crash-free rates, start times, and more. Optimize performance and prevent user churn by addressing critical issues like app hangs, and ANRs. Learn how to keep your iOS app running smoothly across all devices by downloading this eBook.

Get The eBook

Top comments (10)

Collapse
 
hudson-td profile image
Tyler Hudson

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!

Collapse
 
acekuria profile image
Alvin Kuria

From the Odin

Collapse
 
autotelico profile image
Henrique Magalhães

Son of Odin here as well. Loved your article, especially the analogy provided at the end. Makes recursion really stick.

Collapse
 
shahidharith profile image
Shahid

an Odinite too

Collapse
 
itskokeh profile image
Kokeh

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.

Collapse
 
0xkev profile image
Kev

Hello from TOP ^_^

Collapse
 
guillermo_martn_68cb8009 profile image
Guillermo Martín

Hola desde TOP. Excelente articulo, ,uy comprensible.

Collapse
 
syartey007 profile image
S-yartey007

Hello from Odin also and thanks for the excellent explanation

Collapse
 
subhash_r_828f712b9e2c3c6 profile image
Subhash R

Hello, I'm Odinite too!!

Collapse
 
buturum_26c988a5dcacf3fe1 profile image
BUTURUM

Any article used by Odin Project is doomed to be recognised only for being in Odin Project

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up