jarednielsen.com

Big O Recursive Space Complexity

March 20, 2020

jarednielsen big o recursive space complexity

Next to Big O, the second most terrifying computer science topic might be recursion. Don’t let the memes scare you, recursion is just recursion. It’s very easy to understand and you don’t need to be a 10X developer to do so. In this tutorial, you’ll learn the fundamentals of calculating Big O recursive space complexity by calculating the sum of a Fibonacci sequence.

If you’re just joining us, you may want to first read Big O Recursive Time Complexity or start at the beginning with What is Big O Notation?.

What Problem(s) Does Recursion Solve?

  • Recursion allows us to write functions that are compact and elegant.

What Problem(s) Does Recursion Create?

  • Recursion can easily exceed the maximum size of the call stack.
  • Recursion can make the program harder to understand not only for your collaborators, but for your future self

What is Recursion?

In computer science, recursion occurs when a function calls itself within its declaration.

We use recursion to solve a large problem by breaking it down into smaller instances of the same problem.

To do that, we need to tell our function what the smallest instance looks like.

If you recall, with proof by induction we need to establish two things:

  1. base
  2. induction

Recursion is similar. We also need to establish a base case but rather than induction, we establish the recursive case.

We use the recursive case to break the problem down into smaller instances.

We use the base case to return when there are no more problems to be solved.

Time vs. Space Complexity

We were primarily concerned with time complexity up to this point.

When working with recursion we also want to be mindful of space complexity.

Time complexity is how long our algorithms will take to complete their operations.

We’re not concerned with exact or specific times.

We only want to know how one time complexity compares to another time complexity.

Why?

We don’t know what we don’t know.

Our algorithms are not always going to run under the same conditions.

Getting a benchmark on my desktop will be different than getting one on your laptop even if we use the same data set.

Space complexity is how much memory our algorithms will use to complete their operations.

What are we talking about when we talk about memory?

The call stack.

Remember this?

const loop = () => loop();

If you run loop() from your browser console or Node, you’ll get an error.

Why?

Too much recursion!

We constantly add loop() to the call stack until we use up all of the allocated memory.

Then our process yells at us!

That’s called a stack overflow.

The classic metaphors for stacks are cafeteria trays or dishes.

In a cafeteria, clean trays are set out in a stack.

When you line up to get lunch, you take the tray off the top of the stack.

When dirty trays are washed and dried, they are added to the top of the stack.

Same with function calls.

When a function is called, it is added to the stack. When it returns it is taken off the stack.

In the application of life, we need to make a living.

Let’s say I’m a part-time dishwasher.

I go to work, so my work() function is pushed to the stack.

The Stack
work()

My work() function calls three functions.

punchIn()
doDishes(tray)
punchOut()

When I punch in, punchIn() is pushed to the stack.

The Stack
punchIn()
work()

punchIn() immediately returns and is popped off the stack.

Then doDishes() is pushed to the stack.

The Stack
doDishes()
work()

My doDishes() function also calls three functions:

wash()
rinse()
dry()

My doDishes() function also accepts an argument, tray.

For every dish in tray, I push, then pop wash(), rinse() and dry() on and off the stack.

When wash() is called, it is pushed to the stack.

The Stack
wash()
doDishes()
work()

When wash() returns, it is popped off the stack and then rinse() is called and pushed to the stack.

The Stack
rinse()
doDishes()
work()

When rinse() returns, it is popped off the stack and then dry() is called and pushed to the stack.

The Stack
dry()
doDishes()
work()

When dry() returns, it is popped off the stack and then washed() is called again and pushed to the stack.

Wash. Rinse. Dry. Repeat.

When there are no more dishes to do, doDishes() returns, and I punch out and push punchOut() to the stack.

The Stack
punchOut()
work()

It returns immediately and because work is done, work() is popped off the stack.

The Stack
work()

Calculating Recursive Space Complexity

In the previous tutorial, we calculated the time complexity of a naive implementation of the sum of the Fibonacci sequence.

const fibonaive = n => {
   if (n <= 0) {
       return 0;
   } else if (n === 1) {
       return 1;
   };
 
   return fibonaive(n - 1) + fibonaive(n - 2);
};

If the time complexity of our recursive Fibonacci is O(2^n), what’s the space complexity?

Tempted to say the same?

We drew a tree to map out the function calls to help us understand time complexity.

jarednielsen big o recursion fibonacci tree

The branching diagram may not be helpful here because your intuition may be to count the function calls themselves.

Don’t count the leaves.

How deep is the tree?

📝 Space complexity is the amount of memory used by the algorithm.

When a function is called, it is added to the stack.

When a function returns, it is popped off the stack.

We’re not adding all of the function calls to the stack at once.

We are only making n calls at any given time as we move up and down branches.

We proceed branch by branch, making our function calls until our base case is met, then we return and make our calls down the next branch.

For brevity and clarity in the graphics, I’ll refer to our fibonaive() as f().

Let’s say we call f() and pass it a value of 5.

jarednielsen big o recursive space complexity fibonacci tree 01

f(5) is now on the call stack.

Forf(5) to return, it must call itself twice.

But each of those returns must return.

All the way down.

f(5) first calls f(n - 1), which is f(4). So f(4) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 02

And f(4) first calls f(n - 1), which is f(3). So f(3) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 03

And f(3) first calls f(n - 1), which is f(2). So f(2) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 04

And f(2) first calls f(n - 1), which is f(1). So f(1) is pushed to the stack.

What’s our space complexity?

O(n).

Why?

At this point, we are only using n amount of memory.

jarednielsen big o recursive space complexity fibonacci tree 05

We just reached our base case. Our condition is met, so rather than making recursive calls, f(1) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 06

Now f(2) makes its second recursive call, f(n - 2), which is f(0). So f(0) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 07

Our base condition is met, so rather than making recursive calls, f(0) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 08

Both of the recursive calls made by f(2) returned, so f(2) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 09

Now f(3) makes its second recursive call, which is f(n -2) or f(1). So f(1) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 10

We just reached our base case. Our condition is met, so rather than making recursive calls, f(1) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 11

Both of the recursive calls made by f(3) returned, so f(3) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 12

Now f(4) makes its second recursive call, which is f(n -2) or f(2). So f(2) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 13

And f(2) first calls f(n - 1), which is f(1). So f(1) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 14

We just reached our base case. Our condition is met, so rather than making recursive calls, f(1) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 15

Now f(2) makes its second recursive call, f(n - 2), which is f(0). So f(0) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 16

Our base condition is met, so rather than making recursive calls, f(0) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 17

Both of the recursive calls made by f(2) returned, so f(2) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 18

Both of the recursive calls made by f(4) returned, so f(4) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 19

Now f(5) makes its second recursive call, f(n - 2), which is f(3). So f(3) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 20

And f(3) first calls f(n - 1), which is f(2). So f(2) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 21

And f(2) first calls f(n - 1), which is f(1). So f(1) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 22

We just reached our base case. Our condition is met, so rather than making recursive calls, f(1) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 23

Now f(2) makes its second recursive call, f(n - 2), which is f(0). So f(0) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 24

Our base condition is met, so rather than making recursive calls, f(0) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 25

Both of the recursive calls made by f(2) returned, so f(2) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 26

Now f(3) makes its second recursive call, which is f(n -2) or f(1). So f(1) is pushed to the stack.

jarednielsen big o recursive space complexity fibonacci tree 27

We just reached our base case. Our condition is met, so rather than making recursive calls, f(1) returns 1 and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 28

Both of the recursive calls made by f(3) returned, so f(3) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 29

Both of the recursive calls made by f(5) returned, so f(5) returns and is popped off the stack.

jarednielsen big o recursive space complexity fibonacci tree 30

How many calls to f() were on the stack at any given time?

n.

So the space complexity is O(n).

Big O Recursive Space Complexity

In this tutorial, you learned the fundamentals of calculating Big O recursive space complexity. In the next tutorial, we’ll look at how to improve our recursive algorithms with dynamic programming. Stay tuned!


Jared Nielsen

Want to level up your problem solving skills? I write a weekly newsletter about programming, problem solving and lifelong learning. Join now