Recursion Simplified

Recursion Simplified

Recursion is a concept that describes a function calling itself inside itself or simply when a function calls itself. So in other words, the solution to the function depends on the solution to smaller bits (or instances) of the function.

When a recursive function is called, a program stack is generated (imagine an empty open box) and each time the function is called within itself a stack frame is added to the program stack (assume a book is put inside the box per function call, on top of one another). Now, this stack frame stores certain information about the called function. For simplicity, we’ll take note of two - input parameter(s) (as in function argument(s)) and return address (as in the caller of the function).

Two important recursive features to note are:

  • Like loops, it is expected that a recursive function has a base case to avoid stack overflow which is the recursive version of an infinite loop. Therefore, it should be structured in such a way that at a point it stops calling itself, else it infinitely calls itself till the program crashes and it’s never eventually evaluated.

  • There should be smaller input(s) as well each time the function calls itself, a recursive function should be structured in a way that each time it calls itself the input parameter should tend towards the base case.

To illustrate simply, we write a function that calculates the factorial of a number.

let num = 4;
let result = calcFactorial(num);
function calcFactorial(num) {
if (num == 0) {
    return 1;  //cause we know that 0! = 1.
}
return num * calcFactorial(num - 1);
}
console.log(result);

Now, in the evaluation of the result variable:

calcFactorial(4) = 4 x calcFactorial(3)

But calcFactorial(3) = 3 x calcFactorial(2)

But again calcFactorial(2) = 2 x calcFactorial(1)

And once again calcFactorial(1) = 1 x calcFactorial(0)

Once num equals 0, this meets our base case so 1 is returned in place of calcFactorial(0) to its caller calcFactorial(1) and calcFactorial(1) can now be evaluated and return its value to its caller and so on till finally calcFactorial(4) is evaluated. Notice that such a solution (factorial of 4) depends on the solution to smaller bits of the same problem (factorial of 3) and so on.

In JavaScript, the recursive approach is preferred to loops when the problem is complex and repetitive.