Intro To Recursion In JavaScript
Linas Spukas
Posted on January 12, 2020
You can call the same function from within its body, and it is okay until it does not exceed the call stack. The act of a function calling itself is called recursion.
Recursion is very similar to looping. It repeats the same code for multiple times and both need a condition when to stop. Only recursive calls are producing more, smaller function calls.
Each recursive function should have two scenarios: the end and the recursive. The end case is matching the condition and returns from the function, while a recursive case is calling the same function again.
It will make more clear with the following example, where we will log out the countdown numbers from n
to 0:
function countdown(n) {
// end case
if (n <= 0) {
return;
}
// run some code here
console.log(n)
// recursive case
countdown(n-1);
}
countdown(5)
// 5
// 4
// 3
// 2
// 1
// 0
When we first called the function with argument 5
, it first evaluates the end case condition. While the condition is not met, the following code is executed (console logging the number) and reaches the recursive case, which calls the same function with decremented argument. When the number became 0, the end condition is met, the function starts to execute the return
statement and exits the call stack. The whole function call stack looks like that:
countdown(5)
console.log(5)
countdown(5-1)
console.log(4)
countdown(4-1)
console.log(3)
countdown(3-1)
console.log(2)
countdown(2-1)
console.log(1)
countdown(1-1)
console.log(0)
return
return
return
return
return
return
Call Stack
The recursion uses a function call stack. That means every function call is piling up in the stack and gets executed when the function end condition is met and return statement executed. The last function call will be executed the first, that's how the call stack works.
To see it for your self, open the browser console, create a snippet with the countdown
function and set the breakpoint next to the countdown(n-1);
and call the function. In the debugger panel take a closer look to the call stack
pane, which will stack up with each recursive function call.
To better understand what I mean, let's add one more console log to countdown function:
function countdown(n) {
if (n <= 0) {
return;
}
console.log('add to call stack ', n)
countdown(n-1);
console.log('exit call stack ', n)
}
countdown(3)
// add to call stack 3
// add to call stack 2
// add to call stack 1
// exit call stack 1
// exit call stack 2
// exit call stack 3
Recursion vs Loops
Most of the times running loops will be cheaper and more performant then calling a function multiple times. But there are cases where recursion will solve the problems more efficiently. The problems, that consist of many branches and requires exploring. For example, getting the nodes from the DOM tree, where each node can have many children. Or a deeply nested object, where we would need to walk down every level. Or even write a Minimax
algorithm to evaluate the next decision, looking for the best and worst-case scenarios.
Also, recursions are more error-prone, because it is easier to make a conditional mistake, that can lead to infinite recursions.
And need to mention the maximum call stack of the browsers. Every browser has a different call stack limit. So if the data is so big, that requires more recursive calls than the stack can take, the browser will throw an error.
Conclusion
To sum up, we learned a bit that the function that calls itself is called recursive. Function calls are stacked in the browser call stacks and the last call is evaluated the first. Where the recursion makes sense to use and what possible issues it can produce.
Posted on January 12, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
November 29, 2024