Recursion

Recursion is basically a process that calls itself until it reaches the finish condition.

Here's a factorial algorithm as an example:

function factorial(num) {
// End of the recursion
if (num === 1) return num;
// Calls itself decreasing the input by 1
return num * factorial(num - 1);
}

\You can generate a stack overflow here by just using any number smaller than 1*

The processes are stored in a structure called a call stack, which pushes the processes—calls—into the stack and pops them when they are finished.

All recursion algorithms should have the following:

• Return something to get out of the stack

• A condition that ends the recursion (base case)

• A code that changes the input (e.g., incrementing the input)

Benefits:

• Readability of the code

• Elegant solution

• Breakdown the problem into smaller pieces (divide-and-conquer problem approach)

Drawbacks:

• Performance problems with deeply nested calls

• Stack overflow (no base case, no return or returning wrong thing)

• In some cases, more inefficient than iterate solutions (loops)

Where we find recursion in JS:

• JSON.parse() / JSON.stringfy()

• DOM traversal algorithms

• Object traversal algorithms

More deeply into call stack:

• The maximum size depends on the system and browsers (Chrome around 10-20k calls, Node.js around 100k calls)

• In node, you can set the maximum call stack size by calling node --stack-size=Xmb

• To calculate the approximate space consumed by a function call: stack_size = sizeof(arguments) + sizeof(local_variables) + sizeof(return_value) + sizeof(context)