What is recursion and how is it used in JavaScript?

TL;DR

Recursion is a programming technique where a function calls itself to solve a problem. In JavaScript, recursion is used to solve problems that can be broken down into smaller, similar sub-problems. A base case is essential to stop the recursive calls and prevent infinite loops. For example, calculating the factorial of a number can be done using recursion:

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

Definition of recursion

Recursion is a technique in programming where a function calls itself in order to solve a problem. This approach is particularly useful for problems that can be divided into smaller, similar sub-problems. The key components of a recursive function are:

Base case: The condition under which the function stops calling itself, preventing an infinite loop.
Recursive case: The part of the function where it calls itself with a modified argument, moving towards the base case.

Example: Calculating factorial

The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. It can be defined recursively as:

0! = 1 (base case)
n! = n * (n - 1)! for n > 0 (recursive case)

Here is how you can implement this in JavaScript:

function factorial(n) {
  if (n === 0) {
    // base case
    return 1;
  }
  return n * factorial(n - 1); // recursive case
}

Example: Fibonacci sequence

The Fibonacci sequence is another classic example of recursion. Each number in the sequence is the sum of the two preceding ones, usually starting with 0 and 1. The sequence can be defined recursively as:

fib(0) = 0 (base case)
fib(1) = 1 (base case)
fib(n) = fib(n - 1) + fib(n - 2) for n > 1 (recursive case)

Here is how you can implement this in JavaScript:

function fibonacci(n) {
  if (n === 0) {
    // base case
    return 0;
  }
  if (n === 1) {
    // base case
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}

Tail recursion

Tail recursion is a special form of recursion where the recursive call is the last operation in the function. This can be optimized by some JavaScript engines to improve performance and prevent stack overflow. Here is an example of a tail-recursive factorial function:

function factorial(n, acc = 1) {
  if (n === 0) {
    return acc;
  }
  return factorial(n - 1, n * acc);
}

Use cases for recursion

Tree traversal: Recursion is often used to traverse tree structures, such as the DOM or binary trees.
Divide and conquer algorithms: Algorithms like quicksort and mergesort use recursion to divide the problem into smaller sub-problems.
Dynamic programming: Problems like the knapsack problem and certain graph algorithms can be solved using recursion.

What is recursion and how is it used in JavaScript?

TL;DR