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:

Photo of Courtney Menikheim. They are about 5 foot 7, have hair cropped close to their head, except for the top, which hangs over by their jawline. They are smiling at the camera. They wear glasses.

Application Developer

Courtney is an enthusiastic GEODev and member of our Products team. When they aren't helping design and build software, Courtney enjoys playing board games, spending time with their dogs, and gardenining.