For the computational equivalent of dishes, laundry, and dusting–the chores that never end–we have a special programming concept called recursion. Similar to loops, recursion is a common principle in programming that’s used to iterate through a workload a specified number of times. Basically, it’s when a function keeps calling itself to perform its job over and over until you make it stop. While we can’t get computers to take care of all of your housework yet, we have other things we can get them to do.
There are two must-haves for a recursive function:
- An end condition
- A return statement that calls the function
Computers are nice because they do whatever you tell them. If we give a computer the function doDishes, it does dishes like we ask. It goes through a single iteration of whatever action doDishes entails. But what if we have a lot of dishes and we need it to do dishes more than once? We just call it again by placing doDishes in the return statement.
But since computers do whatever you tell them, the function will keep doing dishes until its poor little hands are pruny and it just can’t do them anymore. Since we’re humane programmers that care about our programs, we give the function an end condition. This portion of the statement lets doDishes know when it’s done enough.
In this article, we’ll be using JavaScript to demonstrate some examples of recursive programming.
How to Set Up Recursive Functions
Here’s a generic example of a recursive function.
let doSomething = () => {
// stuff happens
return doSomething();
// stuff happens again
}
Because we call doSomething in the return statement of the function, stuff is going to happen again. And then we call doSomething in the return statement. And then stuff happens again. And stuff is going to keep happening unless we tell it to stop. We have to give the function an order to stop by using an end condition before we can move on to something else.
Recursion is great for small, menial tasks you don’t want to do yourself. Counting down from 15 is pretty annoying. Let’s use that as an example. Feel free to follow along by opening the console log in your browser.
let countToZero = (n) => {
if (n === 0) {
return 0;
} else {
console.log(n);
return countToZero(n - 1);
}
}
countToZero(15);
Our variable n stands for number, but what exactly is happening with it? We passed countToZero the value of 15 and it begins its journey through the function as n. It makes its way to line 2, and if (n === 0) checks to see if 15 equals 0. Clearly, this is wrong, and n starts to execute the else statement. After the console log displays “15” for us, we return countToZero with a new value for n. We performed one iteration through countToZero(15), and returned countToZero(15 – 1). When you call the function in its return, you cause the function to be called again before the function can finalize itself.
This time n is equal to 14. So, countToZero(14) checks to see if 14 equals 0, and yet again it’s not a match. The function refers back to the else statement where we call countToZero(14 – 1), resulting in 13.
The cycle continues.
countToZero(13 – 1) = countToZero(12)
countToZero(12 – 1) = countToZero(11)
countToZero(10)
countToZero(9)
countToZero(8)
You get my point. The cycle doesn’t stop until we meet the end condition. In this case, the end condition is n === 0. And when the function is done with all its hard work, we’re left with a beautiful console log that counts down from 15 to 0.
Call Stack
JavaScript has its own way of prioritizing which orders it handles first. I like to call it the “I’ll deal with it later” way of prioritizing. Every time we call a function before it can finish, JavaScript stops the current function to start the new function. There’s an easy way to remember it.
JavaScript always prioritizes Last In First Out.
Let’s say you go to the library and you get a tall stack of books for your research project. You can’t read all the books at once, so you read each book individually and then set each book in a new stack to keep track of which books you’ve finished. Once you’ve finished reading all the books, the new stack is in the opposite order of the first stack. This is what happens in JavaScript.
One of the best ways to understand this is to look at what’s called a factorial function.
let product = (n) => {
if (n === 1) {
return 1;
}
return n * product(n - 1);
};
let factorialFour = product(4);
console.log(factorialFour)
We start by passing 4 as an argument for parameter n. Since 4 does not equal 1, the function returns 4 * product(4 – 1), i.e. 4 * product(3). Because product(3) is called before product(4) can finish, JavaScript sets aside product(4) to execute later. If we follow the logic in product(3), it returns product(2) before it can finish as well. To deal with this, JavaScript places each function into a “deal with it later” stack called the call stack.
Eventually, we reach our end condition where JavaScript stops receiving functions. When n finally returns 1, JavaScript is left with its stack of “deal with it later” problems. It handles each problem in the new stack one by one, working from top to bottom. The math problem ends up looking like this.
JavaScript starts with the first function in its new stack, product(1). It simply returns 1. But JavaScript still has more functions in its stack to execute. The next equation in the stack, product(2), returns (2 * 1). Function product(3) executes to return (3 * 2), which equals 6. Finally, product(4) executes (4 * 6) leaving us with 24.
Remember how we said JavaScript will keep doing the function until you tell it to stop? Well, it has its own breaking point that we call the call stack limit. The stack of books can only go so high before JavaScript throws its hands in the air, gives up, and says, “That’s it! I can’t take this anymore!” Exceeding the call stack limit causes what’s known as a stack overflow error. Each browser has its own call stack limit, but you really shouldn’t need to reach it.
Main Differences Between Recursion and Loops
Is there really any point using recursive functions instead of for or while loops? Yes, there definitely are. Here are some key differences.
- You don’t have to declare an iterator variable
- Recursive functions aren’t truly infinite
- They can be syntactically shorter and sweeter
With a recursive function, you don’t have to declare another variable like i, the go-to iterator variable. Also, loops can technically be infinite. This would cause all sorts of problems, but the main problem it causes is crashing or freezing a program. Recursive functions will eventually hit a limit to their call stack, so you’ll eventually get thrown out with an error. At least you won’t be completely stuck in an infinite loop.
Lastly, you can make a recursive function pretty short and sweet compared to for loops.
let product = (n) => {
return (n === 1) ? 1 : n * product(n - 1);
};
let factorialFour = product(4);
console.log(factorialFour)
Once you get the hang of it, you can make one-line recursive functions to perform your repetitive program tasks for you.
For more information on recursion versus iteration in JavaScript, check out this official JavaScript documentation that gives highly detailed insight.
FreeCodeCamp has some great examples and tutorials as well.
Ad Caelum 