3 minute read
You've probably heard of recursion and know that it involves writing a function that calls itself again. At first this can be kind of hard to wrap your head around, but I'm going to try to break it down as best as I can.
The Call Stack
main that called a second function inside of itself called
nested, the call stack would first have main put in the stack, then when
nested is called it's put on top of main. Once nested is finished being evaluated and returns it's value to main, main can finish being evaluated and also pushed off the stack. Here's what that would look like:
Recursive vs Iterative
Now let's circle back to recursion. We know that every time we call a function it's put on top of the call stack until it's evaluated and then popped off the top of the call stack. With recursion, you just keep calling the same function and keep pushing it onto the call stack. Obviously you can't just keep calling the same function over and over with no limit, you'll overflow the stack.
To make sure our recursive functions stop being called it's actually pretty similar to a loop. You make a condition that would stop the function from being called at a certain point(this is just like using
i < arr.length; in a for loop). You also have to make sure that every time you call the function recursively that it's getting a different value(this would be kind of like
i++ but not really, you'll see in a moment). So if recursion is similar to a loop why not just iterate? Recursion while confusing at first is very concise and often requires less lines of code to do the same task. Here's an example of the same problem done both iteratively and recursively. Both functions will find the factorial of a given number.
You're probably familiar with a solution like this, there isn't really anything wrong with this solution. It'll work just fine.
As you can see the recursive solution might be a little hard to understand at first. For one, it's a lot less code which is great because it means you can write less code for the same result. At the same time though, it can be hard to see how calling the function within itself is actually working. When returning
num * recursiveFactorial(num -1) the original function waits for this new call to resolve. This continues until the base case is met. So, calling
recursiveFactorial(3) is the same as calling 3 * 2 * 1.
For more information on recursion and the call stack you can checkout these links:
I'll do my best to answer any questions in the comments below and feel free to check out some of my other blog posts as well. Thanks for reading!
If you have any questions please leave a comment over on dev.to