Recursion
Repeating a task is quite common in programs. Maybe something needs to be repeated a certain number of times, or an action needs to be performed for each item in a group, or something needs to keep happening while some condition is true. You’re flush with choices! But these are all considered iterative loops, and sometimes they’re not the best solution.
Your other choice would be recursion. If a function is recursive, this means that it calls itself. Which if it was left at that, this would just lead to an infinite loop of the recursive function calling itself forever. But we can provide the function with a condition where it should not call itself, and this will make a more manageable and useful loop. The trick with a recursive function is to make it solve a little bit of the problem on each loop, and pass the rest of the problem off to the next loop. This will be repeated until the last loop when the problem is something very simple, and will likely return a value instead of calling for another round of the function.
The most common example of recursion is calculating factorial products, or that is, if you have 4! (read: four factorial), you’d want code to break this down to 4 * 3 * 2 * 1, and then perform the math. With a iterative solution, it should look something like this:
function factorial(num) {
let product = 1
if (num <= 1) {
return product
}
while (num > 1) {
product * = num;
num--;
}
return product;
}If we call factorial(4), then a variable called “product” will be declared, assigned a value of 1, and will be the return value. The bulk of the work will be done by the while loop, which loops while the provided argument is greater than 1. For each loop, the product variable will be set to the current value of product multiplied by the argument, and then the argument will be decremented by 1. Pretty straight forward, and handles factorials quite well. Let’s compare this to the recursive counterpart:
function factorial(num){
if (num <= 1) {
return 1
}
return num * factorial(num - 1)
}It’s a few lines shorter, the bulk of the work is done in the return statement, and as expected, it calls itself. Let’s step through this, calling factorial(4):
With the function declared, we provide it an argument of 4. 4 is greater than 1, so the first if statement is ignored. Then we return 4 * factorial (4–1). Good, everything’s done, easy program!
Well, except we need to figure out factorial(4–1) now:
3 is greater than 1, so we ignore the first possible return. Then we return 3 * factorial (3–1). And repeat:
2 is greater than 1, so it returns 2 * factorial (2–1). One last time!
1 is equal to 1, so 1 is returned. That’s a more concrete answer than 2 * factorial(2–1), so it’ll take the place of the callback, and be 2 * 1, or just 2. And then this can be placed into the return statement before that, 3 * factorial(3–1), to make it 3*2, or 6. And once more, 4 * factorial(4–1) becomes 4*6, or 24.
So, there’s some pretty big differences. The first being that I didn’t have to draw out diagrams for the iterative solution. Silly observation, but each one of those extra boxes represents a whole new function call, and in the execution of the program, this means a larger memory requirement. Not that much of a problem, but imagine if it was working out the factorial for a much larger number. Each number would be getting its own function call, and those add up in the memory quick.
And I was going to end on a defense of recursive functions, but the more I look around for good arguments for them, the more I find good arguments against them. Their code is shorter, and their solutions are more elegant, but they’re often slower, they take more memory, they’re often difficult to read and update later, and every recursive function has an iterative counterpart, so there’s always an alternative.
References:
Whole thread is good, but I like this answer and lot, and nicked his code example.
https://stackoverflow.com/a/15346857
I was going to bring this up more in my defense of recursion, but I decided to mostly scrap that. Good read on how recursion is actually pretty good with navigating data structures.
I used their picture for my thumbnail!
I’m not sure how I ran into it, but this thread, and particularly the response from user Michele Moneywell, have a good discussion about the merits for and against recursion.
