Recursion Revealed

photo by @pkmfaris

As a recent software engineering graduate, I've been spending a lot of time readying myself for technical interviews. Part of this process has been learning more about data structures and algorithms. In this post, I'll be discussing why recursion is useful and how we can implement it. I'll also examine two common recursion examples, how to sum numbers from 1 to n and how to reverse a string using recursion.

What is Recursion?

We can say that a function is recursive if it calls itself as a subroutine. Personally, I've found that, while this makes sense in theory, it can take a while to really wrap your head around how recursion works. Essentially what we're doing is breaking something down into smaller problems by calling the function on itself. Once we reach a point where the problem can be solved without being further reduced, we stop the recursion call and return the answer.

When to Use Recursion Rather Than Iteration?

Recursion and iteration can often be used to similarly solve problems. Why then would we choose to implement a recursive solution rather than a straightforward iterative one? Here are some points to take into consideration when deciding:

1. Recursive functions are normally shorter than iterative ones, which can (but doesn't always!) lead to cleaner and more legible code.
2. Recursive solutions are often able to handle more complex problems and structures than iterative solutions. If you're dealing with, for instance, an elaborate tree structure, you'll probably want to use recursion.
3. Iterative functions are generally faster than recursive ones, so if your program is suited to iteration and speed is important, you may want to consider the former.
4. A downside of recursion can be the stack limit. If this is relevant to your function, iteration may be preferable.

Elements of Recursion

When creating a recursive function, we need to include the following elements:

1. A Base Case
   • Usually this is activated when a specific condition is met, for instance when the input reaches 0.
   • When the function reaches the base case, it stops calling itself and returns the result.
2. Logic to Reach Base Case
   • This is where the function performs logic that will bring us closer to the base case.
   • For instance, if the condition for the base case is that the input is equal to 0, this logic could be that 1 is subtracted from the input on each call.
   • Without this logic, we could get stuck in an infinite loop.
3. Recursive Call
   • The recursive call is where we call the function within itself.

photo by @benji3pr

Examples of Recursive Functions

Example 1: Recursively Sum Numbers From 1 to n

In this example, we'll write a function that takes a number, n, and returns the sum of all the numbers from 1 to n:

const recursiveSumToN = (n) => {

  if (n <= 1) {
    return n;
  } else {
    return n + recursiveSumToN(n - 1);
  }

}

recursiveSumToN(5);

// 15

When we call recursiveSumToN(5), we'll get the sum of 1 + 2 + 3 + 4 + 5, which equals 15.

How does this function work? As outlined above, we need a base case, logic to reach the base case, and a recursive call. We can see below which lines of code fulfil each of these responsibilities:

const recursiveSumToN = (n) => {

  if (n <= 1) {
    // BASE CASE: We want to count the numbers from 1 to n, so we need to stop when n === 1.
    return n; 
  } else {
    // LOGIC TO REACH BASE CASE AND RECURSIVE CALL: If n is > 1, we haven't reached our base case, so we need to call our function again.
    return n + recursiveSumToN(n - 1); 
  }

}

recursiveSumToN(5);

// 15

So, for as long as n, i.e. the input, is more than 1, our function calls itself using n - 1. By continuously reducing n by 1, we are working towards the base case and so don't end up in an infinite loop.

The above function can be illustrated like so:

recursiveSumToN(5)
  // this translates to:
  recursiveSumToN(4) + 5
    // =>
    recursiveSumToN(3) + 4
      // =>
      recursiveSumToN(2) + 3
        // =>
        recursiveSumToN(1) + 2
        // 1

The function works in two steps. It repeatedly calls recursiveSumToN until it reaches the base case. Once it fulfils this base case, it begins to resolve the other function calls.

It can also be useful to add some console.logs to our code to see the order in which things are happening:

const recursiveSumToN = (n) => {

    console.log("n: " + n);

    if (n <= 1) {
        console.log("We've hit the base case!");
        return n;
    } else {;
        return n + recursiveSumToN(n - 1);
    }

}

recursiveSumToN(5);

// n: 5
// n: 4
// n: 3
// n: 2
// n: 1
// We've hit the base case!
// 15

So, n decreases by 1 each time until we hit our base case and the function returns our answer.

photo by @robertbye

Example 2: Recursively Reversing a String

In this second example, we're going to look at a function that takes a string, string, and reverses it. This is a problem that can be solved in a number of ways, including iteratively, however we'll take a look at a potential recursive solution:

function recursiveReverseString(string) {

  if (string === "") {
    return ""; 
  }
  else {
    return recursiveReverseString(string.substr(1)) + string.charAt(0);
  }
}

recursiveReverseString("hello");

// olleh

As we can see, the output of this function is the reverse of the original string. In this case "hello" becomes "olleh".

Below, we can see the base case, logic, and recursive call.

function recursiveReverseString(string) {

  if (string === "") {
    // BASE CASE: Once the string is empty, we have reached our base case.
    return "";
  }
  else {
    // LOGIC TO REACH BASE CASE AND RECURSIVE CALL: One character is removed each time the function is called until we reach our base case.
    return recursiveReverseString(string.substr(1)) + string.charAt(0);
  }
}

recursiveReverseString("hello");
// olleh

We can also add some console.logs to see how the string changes with each call:

function recursiveReverseString(string) {

  if (string === "") {
    console.log("string: " + string);
    console.log("We've hit the base case!");
    return "";
  }
  else {
    console.log("string: " + string);
    return recursiveReverseString(string.substr(1)) + string.charAt(0);
  }
}

recursiveReverseString("hello");

// string: hello
// string: ello
// string: llo
// string: lo
// string: o
// string: 
// We've hit the base case!
// olleh

Each time the recursiveReverseString function is called with one fewer character, until we have an empty string. The function then resolves each of the calls and finally outputs the reverse of the original string.

Practice

Being able to implement recursion can be very useful, especially in a technical interview. HackerRank, Codewars, and LeetCode have a variety of recursion-based exercises for you to learn more, develop your skills, and practice.

Sources

1. "When To Use Recursion/When To Use Iteration", CSIE, Accessed November 6, 2020
2. "Principle of Recursion", LeetCode, Accessed November 6, 2020
3. "What is the function of recursion? Why do we need recursion in programming?", Quora, Accessed November 6, 2020
4. "Recursion Explained (with Examples)", Christina McMahon on DEV, Accessed November 6, 2020
5. "Recursion and Stack", Christina McMahon on DEV, Accessed November 6, 2020

Comments

[Athaariq Ardhiansyah]

Beware of stack overflow error (no, it's not a site, it is an error). So the recursion really good at small repetition. However, it might overwhelm the computer if too much repetition, can ended up program to crash.

The solution? Use while loop

Before:

function decrement(n) {
    if(n > 0) {
        return decrement(n-1);
    } else {
        return n;
    }
}
console.log(decrement(10));

After:

function decrement(n) {
    while(n > 10) {
        n -= 1; // This can be n--, actually
    }
    return n;
}
console.log(decrement(10));

Thanks!

[Riccardo Bernardini]

Both examples shown have the advantage of simplicity, but they could be also easily implemented in an iterative way. This could give the impression that recursion is just a fancy way to do something.

I think it would be nice to have also an example of "pure recursion," that is a problem that is easily solved with recursion, but not so easily in an iterative way. The only examples that come to my mind right now are the Hanoi tower and recursive figures like the Sierpiński triangle (the latter can be implemented iteratively using an expansion in base N, but it is not as immediate as the recursive solution).

[Iona Brabender]

Thanks for the comment, Ricardo. As someone who is relatively new to concepts such as recursion, I wanted to explain it in a simple way that would make sense to beginners, as that was the type of material I was looking for when I first started out. Providing more complex examples could be something that I examine in the future.