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.
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.
