Recursion in JavaScript

Recursion is a powerful concept in computer science where a function calls itself in order to solve a problem. It is often used for tasks that can be broken down into smaller, repetitive tasks. In JavaScript, recursion can be a useful tool when working with data structures like trees and graphs, solving mathematical problems, and more.

What is Recursion?

Recursion is a technique where a function calls itself directly or indirectly to solve a problem. Each recursive call works on a smaller instance of the same problem, moving towards a base case that terminates the recursion.

Base Case and Recursive Case

A recursive function typically has two main components:

• Base Case: Every recursive function must have a case that returns a value without performing a recursive call. That case is called the base case. You may write that part of the function first and then test it. There are one or more base cases that are directly solvable without the need for further recursion. Without a base case, it’s the iterative equivalent of writing an infinite loop.
• Recursive Case: Then add the recursive case to the function. Each recursive call moves the solution progressively closer to a base case.

Examples of Recursion

Factorial

The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n.

function factorial(n) {
    // Base case: if n is 0, the factorial is 1
    if (n === 0) {
        return 1;
    }
    // Recursive case: multiply n by the factorial of (n - 1)
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.

function fibonacci(n) {
    // Base cases: the first two numbers of the Fibonacci sequence are 0 and 1
    if (n <= 1) {
        return n;
    }
    // Recursive case: sum of the two preceding numbers
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(7)); // 13

Sum of an Array

Recursively calculate the sum of an array of numbers.

function sumArray(arr) {
    // Base case: if the array is empty, the sum is 0
    if (arr.length === 0) {
        return 0;
    }
    // Recursive case: add the first element to the sum of the rest of the array
    return arr[0] + sumArray(arr.slice(1));
}

console.log(sumArray([1, 2, 3, 4, 5])); // 15

Flattening an Array

Recursively flatten a nested array.

function flattenArray(arr) {
    // Base case: if the array is empty, return an empty array
    if (arr.length === 0) {
        return [];
    }
    // Recursive case: if the first element is an array, flatten it
    // and concatenate with the flattened rest of the array
    if (Array.isArray(arr[0])) {
        return flattenArray(arr[0]).concat(flattenArray(arr.slice(1)));
    }
    // Otherwise, concatenate the first element with the flattened rest of the array
    return [arr[0]].concat(flattenArray(arr.slice(1)));
}

console.log(flattenArray([1, [2, [3, [4]], 5]])); // [1, 2, 3, 4, 5]

Best Practices

1. Define Clear Base Cases
   • Ensure your recursive function has well-defined base cases to prevent infinite recursion.
2. Avoid Excessive Recursion
   • Be mindful of the call stack size. Excessive recursion can lead to stack overflow errors. Consider using iterative solutions or tail recursion optimization if possible.

Memoization

Use memoization to cache results of expensive function calls and avoid redundant calculations.

function fibonacci(n, memo = {}) {
    if (n <= 1) {
        return n;
    }
    if (memo[n]) {
        return memo[n];
    }
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

console.log(fibonacci(50)); // 12586269025

Common Pitfalls

Missing Base Case

Forgetting to include a base case can lead to infinite recursion and a stack overflow error.

Incorrect Recursive Step

Ensure your recursive step moves towards the base case, or the recursion may never terminate.

Stack Overflow

Deep recursion can exceed the call stack size, resulting in a stack overflow error.

function infiniteRecursion() {
    return infiniteRecursion();
}

infiniteRecursion(); // Uncaught RangeError: Maximum call stack size exceeded

Advanced Concepts

Tail Recursion

Tail recursion is a special case of recursion where the recursive call is the last operation in the function. Some languages optimize tail recursion to prevent stack overflow, but JavaScript does not currently support this optimization.

Mutual Recursion

Mutual recursion occurs when two or more functions call each other in a cycle.

function isEven(n) {
    if (n === 0) {
        return true;
    }
    return isOdd(n - 1);
}

function isOdd(n) {
    if (n === 0) {
        return false;
    }
    return isEven(n - 1);
}

console.log(isEven(4)); // true
console.log(isOdd(3)); // true

Recursion Stack Visualization

function memoizedFib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = memoizedFib(n - 1, memo) + memoizedFib(n - 2, memo);
  return memo[n];
}

console.log(memoizedFib(5)); // 5