Recursion Revisited: the Stack

| Comments

A few weeks ago, I wrote a blog post on recursion using an exercise from Codecademy. Shortly after, a blog reader wrote to ask if I could do something similar using this Codecademy exercise.

I was really excited to get some positive feedback, but, as this exercise comes toward the end of the JavaScript Fundamentals course, and I was still near the beginning, I couldn’t jump on it right away. I made a mental note to come back to recursion once I’d put some hours in. Here it goes…

The code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Create an empty array called "stack"
var stack = [];
// Here is our recursive function
function power(base, exponent) {
  // Base case 
  if (exponent === 0) {
    return 1;
  }
  // Recursive case
  else {
    stack[exponent - 1] = base * power(base, exponent - 1);
    return stack[exponent-1];
  }
}
power(3, 3);
console.log(stack);  // Displays [3, 9, 27]

An if statement checks the condition (exponent === 0). If this statement is true, we run the if-block: Return 1.

Otherwise we run the else-block: For the array called stack at index position [exponent - 1], calculate base * power(base, exponent - 1); and return that value.

We totally get recursion, well almost: We initially unpicked recursion here. If you’re struggling to visualise the recursive process, I still think this is a useful starting place. Then get back here, because there’s a problem with the original logic. This has a lot to do with understanding the order in which JavaScript evaluates code.

The stack:

A concept closely related to recursion is a thing called the stack. When a function is called, control is given to the body of that function. When that body returns, the code that called the function is resumed. While the body is running, the computer must remember the context from which the function was called, so that it knows where to continue afterwards. The place where this context is stored is called the stack.

Eloquent Javascript, Chapter 3

JavaScript evaluates code from left-to-right and top-to-bottom, until your code calls a function. Then the interpreter jumps to the called function, and starts evaluating the code there. This new context is pushed to the top of the stack.

Because a function body can call a function, the contexts assigned to temporary memory start to stack. The global context is always at the bottom of the stack; function contexts are heaped on top. Here’s what I think is occurring when we call the power function described above:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
power(3, 3) ... add context to stack
  exponent is > 0 so else applies
  stack[2] = 3 * power(3, 2) ... add context to stack
    exponent is > 0 so else applies
    stack[1] = 3 * power(3, 1) ... add context to stack
      exponent is > 0 so else applies
      stack[0] = 3 * power(3, 0) ... add context to stack
        exponent is = 0 so if applies
      return 1 ... and unwind the stack...
      stack[0] = 3 * 1 = 3
    return 3
    stack[1] = 3 * 3 = 9
  return 9
  stack[2] = 3 * 9 = 27
return 27 ... and back in global ...

Each time a value is returned, we exit the function body we’re in and pop the next function context off the stack (last-on, first-off), until we arrive back in the global environment, and continue on our way. Still not clear? Check out David Shariff’s explanation of the execution context and stack in JavaScript.

Why Care?

Understanding the execution context and stack allows you to know the reasons behind why your code is evaluating to different values that you had not initially expected.

davidshariff.com

Let’s rewind a few weeks to our first look at recursion:

1
2
3
4
5
6
7
8
9
var power = function (base, exponent) {
  if (exponent === 0) {
    return 1;
  } else {
    return base * power(base, exponent - 1);
  }
}

console.log(power(2,3) === 8)

The niggle: If we console.log the returned values, there’s a difference between what we expect and what we get.

Expected returned values: 2 * 2 * 2 * 1 = 8 (ref.)

Actual returned values:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
power(2, 3) ... add context to stack
  exponent is > 0 so else applies
  2 * power(2, 2) ... add context to stack
    exponent is > 0 so else applies
    2 * power(2, 1) ... add context to stack
      exponent is > 0 so else applies
      2 * power(2, 0) ... add context to stack
        exponent is = 0 so if applies
      return 1 ... and unwind the stack...
      2 * 1 = 2
    return 2
    2 * 2 = 4
  return 4
  2 * 4 = 8
return 8 ... and back in global ...

Conclusion

Programmers are professional problem solvers. We limit ourselves unnecessarily if we settle for an incomplete understanding of how our code works. Honestly, if we don’t get something, it just hasn’t been explained the right way. That’s the beauty of feeling discombobulated when you get unexpected coding outcomes: it’s reassuring to know there IS an explanation. A good explanation washes all the frustration away.

Other than that, there’s one more thing I’d like to quickly mention. We can see calling a function multiple times takes memory, sometimes more memory than is feasible. Both our examples could’ve been solved using for loops. While it wouldn’t make much difference either way in the examples given, it’s worth remembering a short solution that makes heavy demands on memory might be replaced with a faster, if less eloquent, solution:

The basic rule, which has been repeated by many programmers and with which I wholeheartedly agree, is to not worry about efficiency until your program is provably too slow. When it is, find out which parts are too slow, and start exchanging elegance for efficiency in those parts.

Of course, the above rule doesn’t mean one should start ignoring performance altogether. In many cases, like the power function, not much simplicity is gained by the ‘elegant’ approach. In other cases, an experienced programmer can see right away that a simple approach is never going to be fast enough.

Eloquent Javascript, Chapter 3

Comments