Recursion

Intro

Recursion can be an intimidating topic. (There's a reason I chose a seemingly endless and slightly sinister-looking spiral staircase for the cover photo of this article). Until a couple of days ago, when asked about recursion, the only real answer I could muster was, "It's a function that calls itself". Which is a true answer, if not a complete one.

As with most challenging or tricky topics, when we break it down into smaller chunks, give ourselves time to digest, and practice, we can get it. So let's try to do some of that now.

Pre-requisites

Some concepts that are important to understand in order to cover this topic are:

Familiarity with JavaScript as this is the language used for the code examples
Loops: for loops, while loops, etc.
A basic understanding of how functions and function calls work (e.g. functions run in a particular order, functions can contain other functions, functions can call other functions.

Note: I have a tendency, for better or worse, to anthropomorphize concepts. I like to think this provides a friendly and low-pressure atmosphere.

Functions Calling Functions

One great thing about functions is that, in most cases, they are orderly and polite. What I mean by that is, they tend to run in a predictable order. We can usually predict the order in which functions will execute. So when we call one function inside another, the outer function will wait for the inner function to complete before completing itself. Let's look at an example of this:

function makeFlashcards(){
    let languages = ["Python", "Java", "JavaScript"];
    languages.forEach((language) => {
        console.log(`Make a ${language} flashcard`);
    })
    return 
}

function watchUdemyVideo(){
    console.log("Watching Udemy Video"); 
    makeFlashcards();
    return 
}

function study(){
    watchUdemyVideo(); 
    console.log("All done studying!")
    return 
}

study()

Bonus: Before moving on to the section below, try and see if you can figure out the order the phrases above will print based on the order of the function calls.

Let's walk through what's happening here.

After we define our three functions (makeFlashcards, watchUdemyVideo, study) we call the study function.
Immediately study calls watchUdemyVideo. Now, study is waiting. It does not move on to the next line yet.
watchUdemyVideo prints "Watch Udemy Video". Then calls makeFlashcards. Now watchUdemyVideo is waiting AND study is still waiting too.
makeFlashcards cycles through the array, languages, and prints a phrase for each flashcard. Then it returns.
Now that makeFlashcards has returned, watchUdemyVideo can stop waiting and return.
After watchUdemyVideo returns, study can stop waiting. It prints "All done studying" and finally returns too.

So in the console, we should see:

Watching Udemy Video
Make a Python flashcard
Make a Java flashcard
Make a JavaScript flashcard
All done studying!

So, now we've demonstrated how functions can call other functions and that each function will wait until the function inside of it is completed.

Recursion is really a continuation of this same idea except, instead of function a calling function b and waiting for function b to return, function a calls itself and waits.

The Call Stack

What we've described, the waiting functions, actually has terminology that we can use to be more precise, the call stack.

The call stack is responsible for managing the order in which functions are executed. When a function is called it is placed on the call stack. When a function returns (finishes executing) it is removed from the call stack. So in the example above, the functions would be added to the call stack as follows:

study is added
watchUdemyVideo is added on top of study
makeFlashcards is added on top of watchUdemyVideo

The functions would be removed from the stack in the following order:

makeFlashcards returns and is removed.
watchUdemyVideo returns and is removed.
study returns and is removed.

Another way to describe this behavior is "last in first out". If this seems confusing or unintuitive, just think, there are real examples of this every day.

Imagine you are making pancakes. You make the first pancake and you add it to the plate. Then you make the second pancake and add it to the plate. You add the second pancake on top of the first and so on. Eventually, you have this stack (ha!) of pancakes. When you're ready to consume your pancakes what do you do? You eat the pancake on top. So the last pancake you made is placed on top of the stack and is the first one you eat. Last in, first out.

Ok, so now that we have a better understanding of functions calling other functions and the call stack let's get to recursion.

Recursion

Earlier, I mentioned that recursion is a function calling itself. Until a few days ago, that was the only way I thought of it. Really, recursion is a tool in our developer toolbox that provides a different way of solving problems.

Let's look at an example below. We can solve the same problem recursively(using recursion) or iteratively (without recursion).

Problem: Write a function that takes a positive integer and returns the product of all the integers from 1 to that integer a.k.a. find the factorial. For example: if the input is 3, the output should be 6 (the product of 3 * 2 * 1)

Given the same inputs, these two functions return the same outputs. (Feel free to try it out here on CodePen.)

Although this is a simple example, with our recursive solution, we didn't have to initiate separate variables product and i or loop through a for loop. Instead, we used the given parameter, a conditional, and a function call.

These are the fundamental components in a recursive solution. Let's take a closer look at them.

3 Parts of the Recursive Function

The Base Case / Conditional
The Recursive Call
The Modified Input

We can gain an understanding of how these components work by examining what happens if we remove them or leave them out:

Without the base case, the recursive function would theoretically run forever (actually the call stack has a limited amount of space so eventually we would see the stack overflow error). Additionally, if we include a base case that doesn't match the changes we make to the input, we end up with the same issue. In the example above, if we kept our base case, but added 1 to num instead of subtracting 1 from num, we would never reach a point where num === 1. It's also important that we have a return statement. If we replaced the return statement with a console.log(1) instead, our recursive function would continue to run. Remember, it the function hitting a return that causes it to finish executing and to be removed from the call stack.
Without the recursive call, none of this works. This may seem obvious, but the function must call itself if the base case has not been met.
Without modifying the input, specifically in a way that moves it towards the base case, the recursive call will never stop. Again, in our example above, if we continued passing num, unmodified, into our factorial function, we would never reach our base case.

Let's step through what's happening. We want to know if the base case has been met and if it has return 1. If not, we want to make another recursive call with a modified input.

When 3 is passed in, we have not met our base case so we return 3 * factorial(3-1). Now factorial(3) is on the call stack, waiting on the return value of factorial(2). (Number 1 on the diagram)

Now 2 is our input. It does not meet our base case. So we return 2 * factorial(2-1). Now factorial(3) and factorial(2) are both on the call stack waiting. (Number 2 on the diagram)

Now our input is 1. It does meet our base case. So factorial(1) returns 1! (Numbers 3 and 4 on the diagram). If we didn't have a base case and return a value, the diagram would go on forever.

Now we can work backwards. factorial(2) can return with 2 multiplied by the value returned from factorial(1) (in this case 1). So 2 * 1 = 2. Now factorial(3) can return. It returns 3 multiplied by the value returned from factorial(2) (which is 2). This leads to 3 * 2 = 6.

All our functions have returned, our stack is empty, and we've got our answer: 6.

Why Does Recursion Matter?

Although the example above was simple, there are times when recursion offers a cleaner solution than an iterative one.

Recursive functions are a great way to learn to step through functions and understand the order that they are called and executed.

It's great for problems that can be broken down into small repetitive tasks.

I Still Don't Get It

If you still don't get it that's ok. Sometimes you have to sit with a concept or idea before it really clicks. Practicing helps. Start simple and work up to more challenging examples. Google Chrome is a great tool because it allows you to step through recursive functions(all functions really) and see what is on the call stack and what is being returned from each function on the stack at each step. Most importantly, don't give up.

Resources:

Tools to practice: