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.