Recursion Basics

Recursion is a powerful concept in programming where a function calls itself directly or indirectly to solve a problem by breaking it down into smaller, similar sub-problems.

Types of Recursion

Direct Recursion

A function is called Directly Recursive if it calls itself within its own body.

function human() {
    // ... logic ...
    human(); // Direct call to itself
}

Indirect Recursion

A function is Indirectly Recursive if it calls another function, which then calls the first function again.

function human1() {
    human2();
}
 
function human2() {
    human1();
}

Structure of a Recursive Function

A typical recursive function in JavaScript consists of three main parts:

1. Base Condition: The exit condition that stops the recursion. Without it, the function would call itself indefinitely, leading to a stack overflow.
2. Logic: The operations performed during each call.
3. Recursive Call: The function calling itself with a modified argument, moving closer to the base case.

Example:

function fun(n) {
    if (n < 1) return; // Base condition
    console.log(n);    // Logic
    fun(n - 1);        // Recursive call
}

Why Stack Overflow occurs in recursion?

If the Base Case is not reached or not defined, the recursion becomes infinite. In JavaScript, each function call is added to the Call Stack. If the stack grows too large and exceeds the allotted memory, a Stack Overflow error occurs.

How memory is allocated for recursion?

• When a function is called, memory is allocated to it on the Call Stack.
• Each recursive call gets its own copy of local variables.
• Once the base case is reached, the function starts returning, and each call's memory is deallocated in reverse order (LIFO - Last In, First Out).

Detailed Example: printFun Trace

Let's trace the execution of the following recursive function:

function printFun(n) {
    if (n < 1) return;
    
    console.log(n);    // Before recursion
    printFun(n - 1);   // Recursive call
    console.log(n);    // After recursion
}
 
printFun(3);

Output:

3
2
1
1
2
3

Recursion Trace:

1. printFun(3) is called. Prints 3. Calls printFun(2).
2. printFun(2) is called. Prints 2. Calls printFun(1).
3. printFun(1) is called. Prints 1. Calls printFun(0).
4. printFun(0) hits Base Case and returns.
5. Back to printFun(1). Prints 1. Returns.
6. Back to printFun(2). Prints 2. Returns.
7. Back to printFun(3). Prints 3. Returns.

Conclusion

Recursion is a fundamental tool in a programmer's toolkit. While the iterative approach (loops) is often more space-efficient, recursion provides a cleaner and more intuitive solution for problems involving tree traversal, sorting, and complex mathematical computations.