Recursion: What is it exactly?

Introduction

What is recursion?

Try typing "recursion" on the Google search box and see what you find. Interesting, isn't it? Google seems to think you have made a typo or something like that. Maybe unlike me, you did not keep clicking on "Did you mean: recursion", thinking you must be crazy. Well, if you did, you are not to blame. No, it is not a typo, it is recursion!

Okay, no, seriously, what is recursion?

According to sparknotes, Recursion is “a programming pattern that involves the use of a procedure, subroutine, function or algorithm that calls itself in a step having a termination condition so that consecutive repetitions are processed up to the critical step where the condition is met, at which time the rest of each repetition is processed from the last one called to the first”.

Simply put, when a function solves a task, in the process it can call many other functions. A case in which a function calls itself is what is known as recursion. An important condition for recursion to occur is the definition of a base case. The base case tells the recursive function when it no longer needs to call itself. It is called the base of recursion because it immediately produces the obvious result.

Recursion can be a very difficult concept to understand for beginners and I remember struggling with it multiple times. In this article, I will attempt to break down recursion in javascript using three examples.

Recursion Examples

1. Creating a countdown

Here, we will write a function that returns the results from a given number n down to 1.

const countdown = num => {
    // first we define the base case
    if (num < 1) {
        return;
    } else {
        console.log(num);
        let nextNum = num - 1;
        countdown(nextNum);
    }
}

The base case is num < 1 because if the countdown were to start from any number less than 1, there would be no result because the countdown is supposed to stop at 1. Therefore, num < 1 returns the most obvious answer making it suitable as a base case, and nothing is returned. However, if num is not 1, then recursion can take place. Taking an example of num = 3:

console.log(num);
// outputs 3

We define another variable called nextNum which is equal to num decreased by 1 so that the recursion is not infinite. This is similar to how variable i in a regular for loop is either increased or decreased after each loop until the given condition is met in order to avoid an infinite loop.

let nextNum = num - 1;

The function itself is then called again so it can be repeated until the base case is met.

countdown(nextNum); // countdown(2)

num is now equal to 2. 2 is still less than 1, so the else block is run again.

console.log(num);
// outputs 2
let nextNum = num - 1; 
// nextNum = 1;
countdown(1);

num then becomes 1. 1 is not less than 1, so the else block is run yet again. After the else block has been run this time, nextNum becomes 0 and therefore num becomes 0 which is less than 1 (the base case). The else block doesn't run again and the final output becomes:

/*
Output
3
2
1
 */

2. Factorial of a number

Here we will find the factorial of a number using a recursive function. The factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 5 = 5 x 4 x 3 x 2 x 1 which is equal to 120.

const factorial = n => {
    if (n === 0) {
        return 1;
    }
    else {
        return n * factorial(n - 1);
    }
}

Here, the base case is n === 0 because the factorial of 0 is 1 (mathematicians deemed it that way 😃 ). If n is greater than 0, then the else block runs.

return n * factorial(n - 1);
// return 5 * factorial(4)

n becomes 4 and the function is called again. 4 is not equal to 0, so the else block is run again.

return n * factorial(n - 1);
// return 4 * factorial(3)

This continues until n becomes 0. A visual way to represent this is:

3. Fibonacci sequence

The Fibonacci sequence is an integer sequence starting with 1 where the sequence of numbers is created by adding the previous two numbers. i.e 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... In this example, we are going to determine the 4th Fibonacci number i.e 3.

Note that when counting the sequence, you start from 0.

const fibonacci = num => {
    if (num <= 1) {
        return 1;
    } else {
        return fibonacci(num - 1) + fibonacci(num - 2);
    }

Here, the base case is num <= 1. The first Fibonacci number (at index 0) is 1 and the second Fibonacci number (at index 1) is also 1. However, if the given number is greater than 1, then the else block runs.

return fibonacci(num - 1) + fibonacci(num - 2);
// return fibonacci(3) + fibonacci(2)

This is visually represented as:

It is therefore evaluated as 1 + 1 + 1 = 3

Resources

To find out more about recursion, check out these articles:

sparknotes.com/cs/recursion/whatisrecursion..

freecodecamp.org/news/how-recursion-works-e..

javascripttutorial.net/javascript-recursive..

freecodecamp.org/news/quick-intro-to-recurs..

Conclusion

Recursion can be used for practically everything regular loops can be used for. It has the advantage of being shorter and simpler. Although it is a difficult concept to grasp at first, with time and more practice, it starts to become easier to follow.