Scala: Recursion, Stacks, and Stack Frames

(I don’t have a publisher yet, but this is a chapter from my new book, which is about Scala and functional programming. This is an early lesson in the book that is sandwiched between two other lessons that are titled, “Basic Recursion,” and “Tail Recursion,” respectively.

Please note that the content has not been through a review process yet, so all errors are most definitely my own.)

Back to top

Introduction: Our current problem

For functions without deep levels of recursion, there’s nothing wrong with the algorithms shown in the previous chapter. I use this simple, basic form of recursion when I know that I’m working with limited data sets. But in applications where you don’t know how much data you might be processing, it’s important that your recursive algorithms are tail-recursive, otherwise you’ll get a nasty StackOverflowError.

For instance, if you run the sum function of the previous lesson with a much larger list, like this:

object RecursiveSum extends App {

    def sum(list: List[Int]): Int = list match {
        case Nil => 0
        case head :: tail => head + sum(tail)
    }

    val list = List.range(1, 10000)  // MUCH MORE DATA
    val x = sum(list)
    println(x)

}

you’ll get a StackOverflowError, which is really counter to our desire to write great, bulletproof, functional programs.

The actual number of integers in a list needed to produce a StackOverflowError with this function will depend on the java command-line settings you use, but the last time I checked the default Java stack size, it was 1,024 kb — yes, kilobytes — just over one million bytes. That’s not much RAM to work with. I write more about this at the end of this lesson, including how to change the default stack size with a java command-line parameter.

I’ll cover tail recursion in the next lesson, but in this lesson I want to discuss the JVM stack and stack frames. If you’re not already familiar with these concepts, this discussion will help you understand the problem. It can also help you debug “stack traces” in general.

If you’re already comfortable with the JVM stack and stack frames, feel free to skip on to the next lesson.

Back to top

What is a “Stack”?

To understand the potential “stack overflow” problem of recursive algorithms, you need to understand the effect of writing recursive algorithms. The first thing to know is that in all computer programming languages there is this thing called “the stack,” or “call stack.”

Official Java/JVM “stack” definition

Oracle provides the following description of the stack and stack frames as they relate to the JVM:

“Each JVM thread has a private Java virtual machine stack, created at the same time as the thread. A JVM stack stores frames, also called “stack frames”. A JVM stack is analogous to the stack of a conventional language such as C — it holds local variables and partial results, and plays a part in method invocation and return.”

Therefore, you can visualize that a single stack has stack frames that look like this:

As that quote mentions, each thread has its own stack, so in a multi-threaded application there are multiple stacks, and each stack has its own stack of frames:

The Java stack

To explain the stack a little more, I edited the following text slightly, but in general, all of this text comes from the free, online version of a book titled, Inside the Java Virtual Machine, by Bill Venners:

“When a new thread is launched, the JVM creates a new stack for the thread. A Java stack stores a thread’s state in discrete frames. The JVM only performs two operations directly on Java stacks: it pushes and pops frames.”

“The method that is currently being executed by a thread is the thread’s current method. The stack frame for the current method is the current frame. The class in which the current method is defined is called the current class, and the current class’s constant pool is the current constant pool. As it executes a method, the JVM keeps track of the current class and current constant pool. When the JVM encounters instructions that operate on data stored in the stack frame, it performs those operations on the current frame.”

“When a thread invokes a Java method, the JVM creates and pushes a new frame onto the thread’s stack. This new frame then becomes the current frame. As the method executes, it uses the frame to store parameters, local variables, intermediate computations, and other data.”

“All the data on a thread’s stack is private to that thread.”

Back to top

What is a “Stack Frame”?

The same chapter in that book describes the “stack frame” as follows:

“The stack frame has three parts: local variables, operand stack, and frame data.”

You can visualize that like this:

The book continues:

“The sizes of the local variables and operand stack, which are measured in words, depend upon the needs of each individual method. These sizes are determined at compile time and included in the class file data for each method.”

That’s important: the size of a stack frame varies depending on the local variables and operand stack. The book describes that size like this:

“When the JVM invokes a method, it checks the class data to determine the number of words required by the method in the local variables and operand stack. It creates a stack frame of the proper size for the method and pushes it onto the stack.”

These descriptions introduce the phrases word size, operand stack, and constant pool. Here are definitions of those terms:

First, word size is a unit of measure. From Chapter 5 of the same book, the word size can vary in JVM implementations, but it must be at least 32 bits so it can hold a value of type long or double.

Next, the operand stack is defined here on oracle.com, but that definition gets into machine code very quickly. For instance, it shows how two integers are added together with the iadd instruction. You are welcome to dig into those details, but for our purposes, a simple way to think about the operand stack is that it’s memory (RAM) that is used as a working area inside a stack frame.

The Java Run-Time Constant Pool is defined at this oracle.com page, which states, “A run-time constant pool ... contains several kinds of constants, ranging from numeric literals known at compile-time, to method and field references that must be resolved at run-time. The run-time constant pool serves a function similar to that of a symbol table for a conventional programming language, although it contains a wider range of data than a typical symbol table.”

Summary

We can summarize what we’ve learned about the stack and stack frames like this:

  • Each JVM thread has a private stack, created at the same time as the thread.
  • A stack stores frames, also called “stack frames.”

We can also say this about what happens when a Java/Scala/JVM method is invoked:

  • When a method is invoked, a new stack frame is created to contain information about that method.
  • Stack frames can have different sizes, depending on the method’s parameters, local variables, and algorithm.
  • As the method is executed, the code can only access the values in the current stack frame, which you can visualize as being the top-most stack frame.

As it relates to recursion, that last point is important. As a function like our sum function works on a list, such as List(1,2,3), information about that instance of the sum function is in the top-most stack frame, and that instance of sum can’t see the data of other instances of the sum function. This is how what appears to be a single, local variable — like the values head and tail inside of sum — can seemingly have many different values at the same time.

One last resource on the stack and recursion

Not to belabor the point, but I want to share one last description of the stack (and the heap) that has specific comments about recursion. This discussion comes from a book named Algorithms, by Sedgewick and Wayne:

There are two important lines in this description that relate to recursive algorithms:

  • “When the method returns, that information is popped off the stack, so the program can resume execution just after the point where it called the method.”
  • “recursive algorithms can sometimes create extremely deep call stacks and exhaust the stack space.”

Analysis

From all of these discussions I hope you can see the problem:

  • When a recursive function calls itself, information for the function is pushed onto the stack.
  • Each time the function calls itself, another copy of the function information is pushed onto the stack. Because of this, a new stack frame is needed for each level in the recursion.
  • As a result, more and more memory (that is allocated to the stack) is consumed as the function recurses.
Back to top

A visual look at the sum function

Given this background information, let’s take a visual look at how the JVM stack and stack frames work by going back to our recursive sum function from the previous lesson. Before the sum function is initially called, the only thing on the call stack is the application’s main method:

Then main calls sum with List(1,2,3), which I show here without the “List” to keep things simple:

The data that’s given to the sum function matches its second case expression, and in my pseudocode, that expression evaluates to this:

return 1 + sum(2,3)

Next, when sum(2,3) is invoked, the stack looks like this:

Again the second case expression is matched inside of sum, and it evaluates to this:

return 2 + sum(3)

When sum(3) is invoked, the call stack looks like this:

Again the second case expression is matched, and that code evaluates to this:

return 3 + sum(Nil)

At this point, sum(Nil) results in another call to sum, and the stack now looks like this:

This time, when sum(Nil) is invoked, this first case expression is matched:

case Nil => 0

This causes sum to return 0, and when it does, the call stack unwinds and the stack frames are popped off of the stack, as shown in this series of images:

In this process, as each sum call returns, its frame is popped off of the stack, and when the recursion completely ends, the main method is the only frame left on the call stack. (The value 6 is also returned by sum to the line that called it in the main method.)

I hope that gives you a good idea of how recursive function calls are popped on and off of the JVM call stack.

Back to top

Manually dumping the stack with the sum example

If you want to explore this in code, you can also see the series of sum stack calls by modifying the sum function. To do this, add a couple of lines of code to the Nil case to print out stack information when that case is reached:

def sum(xs: List[Int]): Int = xs match {
    case Nil => {
        // this manually creates a stack trace
        val stackTraceAsArray = Thread.currentThread.getStackTrace
        stackTraceAsArray.foreach(println)
        // return 0 as before
        0
    }
    case x :: tail => {
        x + sum(tail)
    }
}

Now, if you call sum with a list that goes from 1 to 5:

val list = List.range(1, 5)

you’ll get this output when the Nil case is reached:

java.lang.Thread.getStackTrace(Thread.java:1588)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)

While that output isn’t too exciting, it shows that when the stack dump is manually triggered when the Nil case is reached, the sum function is on the stack five times. You can verify that this is correct by doing the same thing with a List that has three elements, in which case you’ll see the sum function referenced only three times in the output:

java.lang.Thread.getStackTrace(Thread.java:1588)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:13)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)
recursion.SumWithStackDump$.sum(SumWithStackDump.scala:19)

Clearly the sum function is being added to the stack over and over again, once for each call.

I encourage you to try this on your own to become comfortable with what’s happening.

Back to top

Summary: Our current problem with “basic recursion”

I hope this little dive into the JVM stack and stack frames helps to explain our current problem with “basic recursion.” As mentioned, if I try to pass a List with 10,000 elements into the current recursive sum function, I generate a StackOverflowError. Because we’re trying to write bulletproof programs, this isn’t good.

Back to top

What’s next

Now that we looked at (a) basic recursion in the previous lesson, (b) how it works with the stack and stack frames in this lesson, and (c) how basic recursion can throw a StackOverflowError with large data sets, the next lesson shows how to fix these problems with something called “tail recursion.”

Back to top

See also

I didn’t get into the nitty-gritty details about the stack and stack frames in this lesson. If you want to learn more about the stack, here are some excellent resources:

Back to top

Add new comment

The content of this field is kept private and will not be shown publicly.

Anonymous format

  • Allowed HTML tags: <em> <strong> <cite> <code> <ul type> <ol start type> <li> <pre>
  • Lines and paragraphs break automatically.
By submitting this form, you accept the Mollom privacy policy.