Recursion - a scary word that strikes fear into junior developers and bootcamp graduates. But what if I told you that it can be broken down into three simple parts? There are times where solving a problem recursively can be much simpler and more efficient than solving a problem iteratively (using loops). Once understood, recursion will be a welcomed addition to your technology toolbelt even after you've aced your upcoming job interview.

So buckle up, prepare your pen and paper (or favorite code editor) and let's cover recursion!

Introduction to Recursion

If you haven't heard of recursion before, but have heard of loops, you can think of a recursive functions as a less straightforward alternative (but not a replacement) to loops. The main difference between recursion and loops is that recursion is built into a function, whereas a loop gives instructions to lines of code.

Note: Loops and recursive functions are __NOT__ the same! 

There are many advantages and disadvantages to approaching a 
solution iteratively versus recursively.

(but that's for another time)

Recursion is a technique that uses a function which calls itself one or more times until a specific case is met. The three components of a recursive function are as follows:

1. If a recursive function's input meets a certain base case, it returns a value.
2. If not, the recursive function performs operations to change the state of the recursive function's input to get closer to the base case.
3. Then, the recursive function calls itself again with the modified input.

Seems simple enough, right? Let's go into a bit more detail on each component of a recursive function by using a simple countdown function.

Example 1: recursiveCountdown()

For reference, we will be deconstructing the recursive function below:

function recursiveCountdown(number) {
  // Base Case
  if(number <= 0) {
    return 'We have liftoff!'
  }

  // State Modification
  console.log('We are at: ', number)
  number = number - 1

  // Recursive Call
  return recursiveCountdown(number)
}

What this function will do is count down from a given number until the number reaches 0. Once the number reaches 0, then the function will output We have liftoff! . If the number is not yet zero, the function will let us know what number we are at, reduce that number by 1, and then will call itself with the new number.

Component 1: Base Case

...
  // Base Case
  if(number <= 0) {
    return 'We have liftoff!'
  }
...

The base case of our recursiveCountdown() function lets the function know when to stop and return an output. In many cases, a recursive function will return a number - but for our simplified case it will output the statement We have liftoff! once the number reaches 0. By using the less than or equal to symbol, we also account for cases where the function receives a negative number.

Don't let the singularity of base case fool you - there can be multiple base cases in a recursive function.

Component 2: State Modification

...
  // State Modification
  console.log('We are at: ', number)
  number = number - 1
...

The state modification component is crucial to prevent infinite loops. If the input of our recursive function never changed and didn't meet the base case, it would run forever - we would call the same function with the same input, and nothing would change.

For our recursiveCountdown() function, the state modification is subtracting 1 from our number to get closer to our base case where the input number is equal to or less than 0. Very simple!

Component 3: Recursive Call

...
  // Recursive Call
  return recursiveCountdown(number)
...

The final component of a recursive function is the recursive call. This enables the function to call itself again and again until the base case is reached. For more complex recursive functions, we can perform mathematical operations with multiple recursive calls!

Note: We are not modifying our input number in the 
recursive call as we changed our input number in step two. 

In some cases with simple state modification,
you can combine this component with the previous one.

Great! Now that we have our function, if we run recursiveCountdown(10) , we can see the following output:

recursiveCountdown(10)
// We are at:  10
// We are at:  9
// We are at:  8
// We are at:  7
// We are at:  6
// We are at:  5
// We are at:  4
// We are at:  3
// We are at:  2
// We are at:  1
"We have liftoff!"

Example 2: fibonacci()

One such example of a recursive function which utilizes multiple recursive calls is the Fibonacci Sequence. If you are unaware of the Fibonacci Sequence, it is a sequence of numbers (starting with 0 and 1) where the next number in the sequence is the sum of the previous two numbers.

For example, the first few numbers in the Fibonacci Sequence are:

Term 1: 0,
Term 2: 1,
Term 3: 1 = 0 + 1,
Term 4: 2 = 1 + 1,
Term 5: 3 = 1 + 2,
Term 6: 5 = 2 + 3,
Term 7: 8 = 3 + 5,
Term 8: 13 = 5 + 8,
...

Let's create a recursive function that, given an integer fibNumber , will return the fibNumber 'th term of the Fibonacci Sequence.

Creating a Recursive Function

When creating a recursive function, it may be hard to figure out where to start. At this point, analyze the problem and see if we can figure out some information related to any of the three components to determine where we should start.

The first thing that may come to mind is that the Fibonacci Sequence takes the sum of the previous two terms - but how would we implement that?

Step 1: Analyzing our problem

The core concept of the Fibonacci Sequence is that the next term is always going to be the sum of the two previous terms. Let's take the 3rd term for example:

Term 1: 0,
Term 2: 1,
Term 3: 1 = 0 + 1

To get the 3rd term of the Fibonacci Sequence, fibonacci(3) , you must first know fibonacci(2) and fibonacci(1) . Thus, we can write:

fibonacci(3) = fibonacci(2) + fibonacci(1)

If we generalize this and use our fibNumber variable, we can say:

fibonacci(fibNumber) = fibonacci(fibNumber - 2) + fibonacci(fibNumber - 1)

As opposed to our first function, recursiveCountdown() , we have combined component 2 (state modification) with component 3 (recursive call). That's perfectly fine as long as the state modification is easily readable and not complex.

Finally, we can write that in our recursive function as:

  return fibonacci(fibNumber - 2) + fibonacci(fibNumber - 1)

However, when do we know what the previous two terms are if we never have any values to start with? If you recall, we can use base cases to let the recursive function know when to stop and return a value!

Step 2: Adding base cases

From the Fibonacci Sequence, we know that the latest term is always going to be the sum of the two previous terms. Since the first and second terms don't have two previous terms to reference, we define them as 0 and 1 respectively.

Therefore, when we are on the first or second term of the Fibonacci Sequence we see that:

fibonacci(1) = 0
fibonacci(2) = 1

And to get that into the base case format of our recursive function, we can write that as:

  if(fibNumber <= 1) {
    return 0
  }

  if(fibNumber == 2) {
    return 1
  }

As you can see, we now have two base cases. Again, by adding the less than or equal to symbol in the first base case, we can catch any cases where the function receives a negative number.

Step 3: Put it together

Now, if we combine both of these parts together, we can see the following code:

function fibonacci(fibNumber) {
  if(fibNumber <= 1) {
    return 0
  }

  if(fibNumber == 2) {
    return 1
  }

  return fibonacci(fibNumber - 2) + fibonacci(fibNumber - 1)
}

And that's it! We can now test the fibonacci function ourselves - copy and paste the above code into a code editor or console, then run:

fibonacci(6)
# Expected output: 5

fibonacci(9)
# Expected output: 21

Perfect! We have now created the Fibonacci Sequence using a recursive function.

Conclusion and Next Steps

Now that you have made these basic functions, try running fibonacci(34) . What happens?

You may notice that the response is no longer instantaneous; this is because we keep calling the Fibonacci Sequence a factorially large amount of times relative to our input!

Does this mean recursive functions fail once you get to a large enough input?

Decidedly not - we have more advanced methods such as memoization where we can keep track of the recursive function's output for any given input. For example, we can keep track of fibonacci(5) and reference the output when necessary instead of having to call fibonacci(4) and fibonacci(3) . If we don't memoize (yes, memoize and not memorize), fibonacci(4) will call fibonacci(3) and fibonacci(2) , and so on, and so forth.

However, that's a topic for next time - for now, keep practicing simple recursive functions and understand the three fundamental components!