Recursive Functions

What is recursion and why should we care?

Photo by Noah Windler on Unsplash

Recursion is an important concept in computer science. It is a programming technique that involves a function repeatedly calling itself until it reaches a solution. A recursive function, then, is a function that calls itself.

A recursive function involves a recursive call and a base case. A recursive call is the part of the function body that calls itself until a specified condition is met, while the base case is the function’s stopping point. It is important that we have a base case because without it, we would be stuck in an infinite loop. The Educative diagram below is helpful in understanding the flow of a recursive function:

Credit: Educative

Let’s take a look at an example of a recursive function to illustrate the concept:

function printString(myString) {
   console.log(myString[0]);
   if (myString.length > 1) {
      let mySubString = myString.substring(1, myString.length);           
      printString(mySubString); // recursive call
   } else {
      return true; // base case
   }
}

In the above example, we are using recursion to print out each character of a string by first printing out the first character of the string. If the string is more than one character long, we then take a substring of the original string and make a recursive call, repeating this process until the length of our string is only one character — this is our base case, upon which we will exit the recursive function.

In a JavaScript recursive function, the function is repeatedly called until it hits the base case. Only when the base case is reached and provides a solution can the recursive calls be evaluated.

Why do we care about recursion? While recursion is not an appropriate method for every case, it is an important concept to understand. Programming involves recursive thinking, and it can help us to write shorter and more efficient code when used appropriately.

While iterative functions can usually do the same job, recursive functions are simpler to read and understand. Recursive functions are especially powerful in traversing tree structures. Another reason that recursion is important to understand is that many algorithms use recursion. One downside to recursive functions, however, is that they usually require more memory space and tend to be slower than iterative functions.

This diagram explains the difference between iterative and recursive functions. Credit: freeCodeCamp

Strings and arrays are two data structures that especially lend themselves to recursive solutions. We can think of strings as data structures that are composed of smaller, overlapping substrings. Similarly, we can think of the properties of an array as a series of sub-arrays.

A good way of finding a recursive solution to a problem is to apply the following steps:

1. Choose a specific example to illustrate the concept of the problem.

2. Come up with a function that provides a solution to the specific example.

3. Reframe the solution so that recursion is applied. Reword the function so that it invokes itself within the function body.

While the concept of a recursive function can initially be difficult to grasp, the more we practice it, the clearer it becomes.