Call Stack

Overview

The call stack is what a program uses to keep track of method calls. The call stack is made up of stack frames—one for each method call.

For instance, say we called a method that rolled two dice and printed the sum.

First, our program calls rollTwoAndSum. It goes on the call stack:

rollTwoAndSum

That function calls rollDie, which gets pushed on to the top of the call stack:

rollDie

rollTwoAndSum

Inside of rollDie, we call random.randint. Here's what our call stack looks like then:

random.randint

rollDie

rollTwoAndSum

When random.randint finishes, we return back to rollDie by removing ("popping") random.randint's stack frame.

rollDie

rollTwoAndSum

Same thing when rollDie returns:

rollTwoAndSum

We're not done yet! rollTwoAndSum calls rollDie again:

rollDie

rollTwoAndSum

Which calls random.randint again:

random.randint

rollDie

rollTwoAndSum

random.randint returns, then rollDie returns, putting us back in rollTwoAndSum:

rollTwoAndSum

Which calls print:

print

rollTwoAndSum

The Space Cost of Stack Frames

Each method call creates its own stack frame, taking up space on the call stack. That's important because it can impact the space complexity of an algorithm. Especially when we use recursion.

For example, if we wanted to multiply all the numbers between 1 and n, we could use this recursive approach:

What would the call stack look like when n = 10?

First, product1ToN gets called with n = 10:

    product1ToN    n = 10

This calls product1ToN with n = 9.

    product1ToN    n = 9

    product1ToN    n = 10

Which calls product1ToN with n = 8.

    product1ToN    n = 8

    product1ToN    n = 9

    product1ToN    n = 10

And so on until we get to n = 1.

    product1ToN    n = 1

    product1ToN    n = 2

    product1ToN    n = 3

    product1ToN    n = 4

    product1ToN    n = 5

    product1ToN    n = 6

    product1ToN    n = 7

    product1ToN    n = 8

    product1ToN    n = 9

    product1ToN    n = 10

Look at the size of all those stack frames! The entire call stack takes up space. That's right—we have an space cost even though our method itself doesn't create any data structures!

What if we'd used an iterative approach instead of a recursive one?

This version takes a constant amount of space. At the beginning of the loop, the call stack looks like this:

    product1ToN    n = 10, result = 1, num = 1

As we iterate through the loop, the local variables change, but we stay in the same stack frame because we don't call any other functions.

    product1ToN    n = 10, result = 2, num = 2

    product1ToN    n = 10, result = 6, num = 3

    product1ToN    n = 10, result = 24, num = 4

In general, even though the compiler or interpreter will take care of managing the call stack for you, it's important to consider the depth of the call stack when analyzing the space complexity of an algorithm.

Be especially careful with recursive functions! They can end up building huge call stacks.