Introduction to Recursion in JavaScript

Recursion is a powerful concept in programming that allows us to solve complex problems more efficiently. In JavaScript, recursion can simplify tasks that would otherwise require lengthy and complicated loops. Understanding recursion is essential for tackling advanced topics like dynamic programming and data structures.

What is Recursion?

Recursion is a process where a function calls itself directly or indirectly. A recursive function keeps breaking down a problem into smaller instances of the same problem until it reaches a base condition, which stops the recursion. This approach can be highly effective in simplifying complex problems.

Recursion vs. Loops

While loops iterate in a single direction, moving from one step to the next until a condition is met, recursion works differently. Recursion moves in two directions:

Forward - As the function calls itself, it progresses toward the base condition.
Backward - After reaching the base condition, the function starts returning, solving parts of the problem as it unwinds.

This bidirectional nature of recursion allows it to handle complex tasks that loops might struggle with.

Call Types of Recursion

There are generally two types:

Direct Recursion

A function calls itself directly:

function fun(n) {
    if (n <= 0) return;
    console.log("nedcod.com");
    fun(n - 1);
}

Indirect Recursion

A function calls another function, which in turn calls the first one:

function fun1() {
    fun2();
}
 
function fun2() {
    fun1();
}

Structure of a Recursive Function

A typical recursive function in JavaScript has three main components:

Base Condition: This is the exit condition that stops the recursion. Without it, the function would call itself indefinitely, leading to a stack overflow.
Logic: The core logic that performs the main task, usually involving calculations or processing.
Recursive Call: The function calls itself with a modified argument, moving closer to the base condition.

What is the base condition in recursion?

The base case is a condition that stops further recursive calls. Without it, the recursion becomes infinite, like a never-ending loop.

Here’s a general template for a recursive function:

function recursive() {
    // Base exit condition
    if (/* base condition */) {
        return;
    }
 
    // Logic
    // Perform the necessary operations here
 
    // Recursive call
    recursive();
}

Note: If the base condition is incorrect or unreachable, it causes stack overflow.

Why Stack Overflow error occurs in recursion?

If the base case is not reached or not defined, then the stack overflow problem may arise. Let us take an example to understand this.

How memory is allocated to different function calls in recursion?

In JavaScript, when a function is called, memory is allocated to it on the call stack.

In the case of recursion, each recursive call:

Gets its own copy of local variables
Is added on top of the previous call in the stack When the base case is reached, the function starts returning, and each call’s memory is deallocated in reverse order (LIFO – Last In, First Out).

function printFun(test) {
    if (test < 1)
        return;
    else {
        console.log(test);        // before recursion
        printFun(test - 1);       // recursive call
        console.log(test);        // after recursion
    }
}
 
let test = 3;
printFun(test);
 
let test = 9;
printFun(test);

Example 1: Simple Recursion

Let’s start with a simple example that prints all elements of an array using recursion:

const array = [10, 22, 30, 4, 7];
 
function print(array, startIndex) {
    // Base exit condition
    if (startIndex >= array.length) {
        return;
    }
 
    // Logic
    console.log(array[startIndex]);
 
    // Recursive call
    print(array, startIndex + 1);
}
 
print(array, 0);

In this example, the function print recursively prints each element in the array, moving from the first to the last index.

Example 2: Reverse Printing Using Recursion

Now, let's modify the above function to print the array elements in reverse order:

function revPrint(array, startIndex) {
    // Base exit condition
    if (startIndex >= array.length) {
        return;
    }
 
    // Recursive call
    revPrint(array, startIndex + 1);
 
    // Logic
    console.log(array[startIndex]);
}
 
revPrint(array, 0);

Here, the function first makes the recursive call and then prints the current element. This approach effectively reverses the order of printing.

Example 3: Factorial Calculation

Recursion is often used to solve mathematical problems like calculating the factorial of a number:

function factorial(num) {
    // Base case
    if (num === 0 || num === 1) {
        return 1;
    }
    return num * factorial(num - 1);
}
 
console.log(factorial(4)); // Output: 24

In this example, the factorial of n is calculated by multiplying n with the factorial of n-1, and the recursion continues until it reaches the base case where num is 0 or 1.

Example 4: Summing Array Elements

Here's a recursive function to sum all the elements in an array:

function sumArrayElement(array, startIndex) {
    // Base case
    if (startIndex >= array.length) {
        return 0;
    }
    return array[startIndex] + sumArrayElement(array, startIndex + 1);
}
 
console.log(sumArrayElement(array, 0)); // Output: 73

In this example, the function recursively adds each element of the array, moving from the first to the last element.

Example 5: Single Recursive Call

// T(n) = T(n/2) + C → Time Complexity: Θ(log n)
function singleRecursiveCall(n) {
    if (n <= 1) return; // Base case: T(1) = C
    console.log("Work at n =", n); // Constant work: C
    singleRecursiveCall(Math.floor(n / 2)); // One recursive call: T(n/2)
}
 
singleRecursiveCall(16);

Explanation (One-liner): At each level, problem size halves with constant work, forming a log-depth chain.

Example 6: Two Recursive Calls

T(n) = 2T(n/2) + C → Time Complexity: Θ(n)
function twoRecursiveCalls(n) {
    if (n <= 1) return; // Base case: T(1) = C
    console.log("Work at n =", n); // Constant work: C
    twoRecursiveCalls(Math.floor(n / 2)); // First recursive call
    twoRecursiveCalls(Math.floor(n / 2)); // Second recursive call
}
 
twoRecursiveCalls(16);

Explanation (One-liner): Each level does double the calls with constant work, summing to linear work overall.

Example 7: Print N to 1 Using Recursion

// Approach 1: Iterative
// Use a simple loop that prints from N down to 1.
// Recursive function to print from N to 1
function printReverseOrder(N) {
  for (let i = N; i > 0; i--) {
    console.log(i);
  }
}
 
const N = 5;
printReverseOrder(N);
 
// Approach 2: Recursive
// We will use recursion to break the problem into smaller subproblems.
 
// Recursive function to print from N to 1
function printReverseOrder(N) {
  if (N <= 0) {
    return;
  } else {
    console.log(N);
 
    // recursive call of the function
    printReverseOrder(N - 1);
  }
}
 
const N = 5;
printReverseOrder(N);

Example 8: Print 1 to N

// Iterative Approach
// Use a simple loop from 1 to N.
 
function printIncreasingIterative(N) {
  for (let i = 1; i <= N; i++) {
    console.log(i);
  }
}
printIncreasingIterative(10);
 
// Recursive Approach
// We solve the problem using recursion by printing the smaller numbers first, then the current number.
  printNos(n) {
    if (n > 0) {
      this.printNos(n - 1);
      console.log(n);
    }
    return;
  }
 
printNos(10);

Example 9: Print 1 to N

Example 10: Print 1 to N

Why Recursion is Different from Loops

Bidirectional Execution: Unlike loops, recursion processes the function in both forward and backward directions, making it more flexible and powerful in certain scenarios.
Simplification: Recursive solutions often simplify complex problems and reduce lengthy loops into concise functions, enhancing code readability and maintainability.

Structural Types of Recursion

Recursion can be categorized into several types:

Tail Recursion: The recursive call is the last operation in the function.
Head Recursion: The recursive call is the first operation, followed by other operations.
Tree Recursion: The function makes multiple recursive calls.
Indirect Recursion: A function calls another function, which in turn calls the first function.
Nested Recursion: Recursive function is passed as an argument to itself.

How Recursion Works

Recursion works by leveraging the call stack, a data structure that stores information about active functions. Each time a recursive function is called, a new frame (or instance) is added to the stack. When the base condition is met, these frames are popped off the stack as the function unwinds.

Generalization

Recursion can handle complex problems by breaking them into simpler sub-problems. This divide-and-conquer strategy is effective for tasks like sorting, searching, and traversing hierarchical structures like trees.

Recursion and the Stack

Each recursive call occupies stack space. If a recursion lacks a proper base case or involves too many calls, it may lead to a stack overflow error. Understanding stack operations is crucial to write efficient recursive functions.

Recurrence Relation and Time Complexity

Recurrence relations are mathematical equations that describe the time complexity of recursive algorithms. For example, the recurrence relation for calculating factorial is:

[ T(n) = T(n-1) + O(1) ]

This implies a linear time complexity, or ( O(n) ), for this algorithm. Similarly, different problems result in different recurrence relations, which can be analyzed to determine the algorithm's efficiency.

Static and Global Variables in Recursion

Static Variables

Static variables retain their values across recursive calls. In JavaScript, closures or external variables can mimic this behavior.

Global Variables

Global variables can also hold states across recursive calls, but their use is discouraged due to potential side effects and reduced readability.

let counter = 0;
 
function staticExample() {
    if (counter >= 5) {
        return;
    }
    console.log(counter);
    counter++;
    staticExample();
}
 
staticExample();

Structural Types of Recursion

Tail Recursion

In tail recursion, the recursive call is the last operation in the function. It can be optimized by some compilers to avoid stacking frames.

function tailRec(n) {
    if (n > 0) { // Traditional condition
        console.log(n); // Print first
        tailRec(n - 1); // Recursive call happens last
    } else {
        return; // Base case
    }
}
 
tailRec(5); 
 
// Countdown for a Timer
// Imagine setting a countdown timer where the number decreases until it reaches zero.
 
function countdownTimer(seconds) {
    if (seconds > 0) { // Traditional condition
        console.log(`⏳ ${seconds} seconds remaining...`);
        countdownTimer(seconds - 1); // Recursive call happens at the end
    } else {
        console.log("🚀 Time's up!");
        return; // Base case
    }
}
 
countdownTimer(5); 
/* Output:
   ⏳ 5 seconds remaining...
   ⏳ 4 seconds remaining...
   ⏳ 3 seconds remaining...
   ⏳ 2 seconds remaining...
   ⏳ 1 second remaining...
   🚀 Time's up!
*/

The recursive call is the last thing executed in the function.

function tail(n) {
    if (n === 0){
        return;
    }
    console.log(n);
    tail(n - 1); // ✅ Tail recursion
}

Head Recursion

In head recursion, the recursive call occurs first, followed by other operations.

function headRec(n) {
    if (n > 0) { // Traditional condition
        headRec(n - 1); // Recursive call happens first
        console.log(n); // Print after recursion returns
    } else {
        return; // Base case
    }
}
 
headRec(5); 
 
// 🗄️ Opening Nested Folders
// Imagine opening a deeply nested folder structure until you reach the last folder.
 
function openFolders(depth) {
    if (depth > 0) { // Traditional condition
        openFolders(depth - 1); // Recursive call happens first
        console.log(`📂 Opened folder at depth: ${depth}`);
    } else {
        return; // Base case
    }
}
 
openFolders(5); 
/* Output:
   📂 Opened folder at depth: 1
   📂 Opened folder at depth: 2
   📂 Opened folder at depth: 3
   📂 Opened folder at depth: 4
   📂 Opened folder at depth: 5
*/

The recursive call happens first, and other operations follow it.

function head(n) {
    if (n === 0){
        return;
    }
    head(n - 1); // ⬅️ Recursive call first
    console.log(n); // ⬅️ Operation after
}

Tree Recursion

In tree recursion, a function makes multiple recursive calls.

function treeRec(n) {
    if (n <= 1) { // Traditional condition
        return n; // Base case
    } else {
        return treeRec(n - 1) + treeRec(n - 2); // Calls itself twice
    }
}
 
console.log(treeRec(5)); // Output: 5
 
// 📈 Fibonacci Series for Stock Prediction
// Stock market analysts predict stock prices based on previous trends, just like Fibonacci numbers!
 
function predictStock(n) {
    if (n <= 1) { // Traditional condition
        return n; // Base case
    } else {
        return predictStock(n - 1) + predictStock(n - 2); // Calls itself twice
    }
}
 
console.log(predictStock(5)); // Output: 5

A function makes more than one recursive call.

function tree(n) {
    if (n === 0){
        return;
    }
    tree(n - 1);
    console.log(n);
    tree(n - 1); // Two calls: forms a tree
}

Indirect Recursion

In indirect recursion, one function calls another, which in turn calls the first function.

function funA(n) {
    if (n > 0) { // Traditional condition
        console.log("A:", n);
        funB(n - 1); // Calls funB
    } else {
        return; // Base case
    }
}
 
function funB(n) {
    if (n > 0) { // Traditional condition
        console.log("B:", n);
        funA(n - 2); // Calls funA
    } else {
        return; // Base case
    }
}
 
funA(5);
 
// 🔄 Parent and Child Asking Questions
// A child asks a parent if they can go outside. The parent asks if they have finished homework, and the child asks again when finished.
function childAsk(n) {
    if (n > 0) { // Traditional condition
        console.log(`👶 Child: Can I go outside? (${n})`);
        parentResponse(n - 1); // Calls parent
    } else {
        console.log("👶 Child: Yay! I'm going outside! 🚀");
        return; // Base case
    }
}
 
function parentResponse(n) {
    if (n > 0) { // Traditional condition
        console.log(`👨‍👩‍👦 Parent: Finish your homework first! (${n})`);
        childAsk(n - 2); // Calls child back
    } else {
        return; // Base case
    }
}
 
childAsk(5);
/* Output:
   👶 Child: Can I go outside? (5)
   👨‍👩‍👦 Parent: Finish your homework first! (4)
   👶 Child: Can I go outside? (2)
   👨‍👩‍👦 Parent: Finish your homework first! (1)
   👶 Child: Yay! I'm going outside! 🚀
*/

Nested Recursion

In nested recursion, the recursive call itself contains another recursive call.

function nestedRec(n) {
    if (n > 100) { // Traditional condition
        return n - 10; // Base case: stop when n > 100
    } else {
        return nestedRec(nestedRec(n + 11)); // Call itself inside another call
    }
}
 
console.log(nestedRec(95)); // Output: 91
 
// 📦 Unpacking a Multi-Layered Gift Box
// Imagine a gift box with many layers of wrapping. You have to unwrap multiple times before reaching the final gift.
 
function unwrapGift(layers) {
    if (layers > 5) { // Traditional condition
        return layers - 2; // Stop unwrapping when layers are less than 5
    } else {
        return unwrapGift(unwrapGift(layers + 3)); // Call itself inside another call
    }
}
 
console.log(`🎁 Final Unwrapped Layers: ${unwrapGift(2)}`); // Output: 5

A function is passed as an argument to itself or returns a recursive call inside another.

function nested(n) {
    if (n <= 1){
        return n;
    }
    return nested(nested(n - 1)); // Recursion within recursion
}

Recursion Type	Real-Life Example	Where It Is Used
Tail Recursion	⏳ Countdown Timer	Loop optimization, iterative processing
Head Recursion	📂 Opening Nested Folders	Parsing hierarchical structures, directory traversal
Tree Recursion	📈 Fibonacci Series for Stock Prediction	Dynamic programming, problem-solving algorithms
Indirect Recursion	👨‍👩‍👦 Parent-Child Q&A	Mutual dependency handling, OS scheduling
Nested Recursion	🎁 Unwrapping a Multi-Layered Gift	Complex mathematical computations, AI decision trees

Advantages:

Simpler and cleaner code for problems like:
Tree Traversals
Tower of Hanoi
Divide-and-conquer algorithms
Naturally fits problems where the solution involves solving smaller subproblems

Disadvantages:

More memory usage: Each call is added to the call stack until base case.
Slower execution: Due to overhead of multiple function calls.
Risk of stack overflow if base case is missing or incorrect.

Recursive solutions can always be rewritten iteratively using a loop and a stack.

Conclusion

Recursion is not just a programming technique; it’s a mindset. By breaking down complex problems into simpler sub-problems, recursion enables more efficient and elegant solutions. Understanding its mechanics, types, and applications is vital for any developer looking to master advanced algorithms and data structures.

Analysis of Common Loops Searching Algorithms