A Beginner’s Guide to Recursion

Have you ever been writing code and found yourself breaking down data into smaller and smaller pieces, only to perform the same operation? If your code is starting to look like Russian Nesting Dolls, it might be time to explore recursion. Read on to find out what recursion is, how it can help you, and when to use it.

Sometimes, there are simpler solutions than nesting dolls. Image Source

What is Recursion?

One of the best definitions of recursion I’ve found is this one:

To solve a problem, solve a subproblem that is a smaller instance of the same problem, then use the solution to that smaller instance to solve the original problem.

from Khan Academy

Recursive solutions are usually shorter than iterative ones, and – once a developer is familiar with recursion – can be easier to read. It is also faster to write and easier to support. At the same time, there are some considerations to keep in mind when using recursion, which we’ll touch on later.

Recursion Example

Recursion is especially useful when working with data that is recursive itself. For example, consider a challenge to sum some of the numbers in the Fibonacci sequence. The user will tell the function how many numbers in the sequence to sum. The method will then calculate the appropriate numbers in the sequence and sum them. In JavaScript, that solution would look something like this:

var fibonacciSum = function(numbersToSum, firstNum, secondNum) {
  if(!firstNum) { firstNum = 0; } // The first number in Fibonacci sequence
  if(!secondNum) { secondNum = 1; } // The second number


  // Decrement the numbersToSum, as that's our counter for checking how many values to use
  numbersToSum--;

  //check to see if the desired result is achieved
  if(numbersToSum == 1){
      return firstNum + secondNum;
  } else {

      // If not, continue the process with the next numbers in the sequence
      var nextNum = firstNum + secondNum;
      var sum = firstNum + fibonacciSum(numbersToSum, secondNum, nextNum);
      return sum;
  }
}

Say the user wants to know the sum of the first four Fibonacci numbers. They would call fibonacciSum(4), and the code would return 4 (0+1+1+2). If they called for the sum of the first 7 numbers in the sequence, the code would return 20 (0+1+1+2+3+5+8).

Considerations

Once you get your head around recursive functions, they can be a lot easier to write, read, and maintain than iterative approaches. That being said, it is important to keep in mind the memory used for each function call is reserved until all successive calls in the chain are complete.

Be conscious of how much memory you use. Image Source
Want to learn more? Check out these articles:

Application Developer

Courtney is an enthusiastic and motivated GEODev with a focus on web development. As a member of our Professional Services team, Courtney works on building custom Web Appbuilder Widgets and stand-alone applications. When not working, Courtney relaxes by gardening, practicing shotokan karate, and playing board games.