Recursion is notoriously simple but also confusing, once you start thinking about it. It tends to twist my brain into knots. My goal in this article is to briefly sum up what recursion is, what it’s useful for, and why you should want to learn more about it.
We’ll look at a favorite example of recursive functions: finding a factorial of a number. Then we’ll compare it to a version of a similar function which uses loops to arrive at the same goal.
What is recursion? (in programming)
In short, recursion in programming involves a process where one function calls itself in the course of executing the function.
Recursive functions must have 2 components: a base case and a recursive case.
What are those?
Base case: refers to what logic needs to happen to end the recursive function - otherwise the function will run forever! yikes!
Recursive case: refers to what logic happens over and over again that calls itself within the function
Example A: retrieving the factorial of a number (recursively)
In this example we are going to retrieve the factorial of a number using a recursive function. Note that the factorial is only found for positive numbers. The factorial of 5, for example, is defined as:
$$5! = 54321$$
Here’s the recursive function to calculate the factorial of any positive number:
const factorial = (x) => {
if (x === 1){
return 1;
} else {
return x * factorial(x-1); // the function calls itself
}
};
console.log(factorial(5)) // we should see 120 in the console
The base case is if (x===1) return 1 . This condition will execute if the number fed into factorial is 1, and end the recursive loop.
The recursive case is return x * factorial(x-1) which will run again and again until the base case is reached. Notice that the function factorial is calling itself. That is what makes it recursive.
Example B: retrieving the factorial of a number (loopily)
const factorialLoop = (x) => {
let number = 1;
for (let i=0; i<x; i++){
number *= i;
}
return number;
};
console.log(factorialLoop(5)) // we should still see 120 in the console!
In the above example, instead of using recursion, we use a loop. We set a variable number equal to 1 to keep track of what number the factorial is going to be equal to, and then we loop through all integers between 0 and x (denoted by the variable i) to get a result which is number multiplied by whatever integer i is set to in that iteration. At the end we return the result, which is number.
As you can see we get the same result, but the recursive function is possibly easier to read, as you do not have to parse the looping. (However, I’d guess this is entirely a matter of taste - I personally have found recursive functions extremely difficult to parse in my imagination for a very long time, while loops are more straightforward to me since programming tends to favor them.)
What is it useful for?
Recursion is useful in any situation where you have one operation that needs to be repeated any number of times until a certain condition is met. Instead of using a loop, you can write a function which calls itself. This is succinct and may be easier to read.
Additionally, recursion allows us to break large and complex problems into smaller subproblems that are repeated, instead of trying to tackle one huge problem. It brings some order into a space where confusion may reign supreme.
Why should you want to learn more about it?
Mostly because recursion is cool! But in general, because when you have a set of operations that need to be repeated over and over until a certain condition is met, a recursive function often may be simpler to understand than a function that utilizes a loop.
Note that recursion doesn’t exactly come with any performance benefit - recursive functions take more memory to execute than looped functions, so if you are operating on a large amount of data you may prefer the looped option. The use of recursion is purely for the benefit of the developer reading the code. If it doesn’t appeal to you, it may not be the best choice.