Last time we got a brief introduction, or refresher, into the coding pattern recursion. In the second part of the post series on recursion, we’re going to finish up from where we last stopped.
We ended going over the most commonly used recursion example Factorial. It was a pretty basic example, so nothing would’ve been too much for you to have major issues comprehending. Today we’re taking that knowledge up a notch with a bit more complex example.
Before digging into that, let’s do a quick review on the guiding principles of a recursive development pattern
- Base Case: This specifies when the recursion should end, the requirement for recursion. In our prior exercise, the base case was if(n === 0).
- Calling a subset of a parameter: A recursion is created by a function calling itself inside its scope on a subset of a parameter. This is done by subtracting the parameter by 1 on every function run. In our prior example, ours was factorial(n – 1).
- The function calls itself: Not much to add here, but it’s very important!
Now that we have that quick catch up out of the way, let’s get into the code stuff!
The Stack
In short, the stack can be defined as the context of a function. It contains all the details of that function call at the time of execution: local variables, contents of this, arguments, etc. So with that in mind, what do you think happens to this context in a method where the function calls a method inside itself? Well, simply put:
- The current method is paused
- The context of that method is stored in the execution context stack
- The called method is fired
- After it finishes, the paused method resumes
To better illustrate, let’s take a look back at our factorial method from part 1.
function factorial(n) {
if(n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
So let’s say we’re calling factorial(5). The context would start as {n: 5, at line 1}. As the function continues, it would make a stop at line 4(Context: {n: 5, at line 4}). Which is where are sub-method calls begin. When this call is made a new context is added to the top of the stack, the current method is paused, and its sub-method call begins.
So at this point, our stack should look something like this:
[
Context: {n: 4, at line 1},
Context: {n: 5, at line 4}
]
Looking at in the context of an array, we see that the sub-method call starts and takes precedence over its parent. From that, we can also see that as soon as that method is done the original call would then resume with the returned value of the sub-method that was invoked. So by the time we make it to our last sub-call, our stack should look like this:
[
Context: {n: 0, at line 2},
Context: {n: 1, at line 4},
Context: {n: 2, at line 4},
Context: {n: 3, at line 4},
Context: {n: 4, at line 4},
Context: {n: 5, at line 4}
]
Once n makes it down to 0, that’s when our stack begins to exit. As you see on that line, the first return value would be 1. From there you can just multiply backward from the values we see as n in our stack. Which would be 1 * 1 * 2 * 3 * 4 * 5. So the final returned value would be 120.
At its core, that’s the gist of what a recursion does and others you in performance. Now with that understanding, later on, we’ll be doing some comparisons between recursion and iteration with real-world examples!