Sign InSign Up
Back to Tutorials

JavaScript Recursion

Recursion is a powerful technique where a function calls itself to solve problems. It's especially useful for working with nested data structures and problems that can be broken into smaller subproblems.

Try It Yourself

Explore different recursive functions and see how they work:

index.js
// Recursion examples - try modifying them!

// 1. Countdown (simple recursion)
function countdown(n) {
  if (n <= 0) {
    console.log("Done!");
    return;
  }
  console.log(n);
  countdown(n - 1);
}

console.log("--- Countdown ---");
countdown(5);

// 2. Factorial
function factorial(n) {
  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1); // Recursive case
}

console.log("\n--- Factorial ---");
console.log("5! =", factorial(5));

// 3. Sum of array
function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}

console.log("\n--- Array Sum ---");
console.log("Sum [1,2,3,4,5] =", sumArray([1, 2, 3, 4, 5]));

What is Recursion?

Recursion is when a function calls itself to solve a problem. Each call works on a smaller piece until reaching a base case that stops the recursion.

javascript
// Basic structure of a recursive function
function recursiveFunction(input) {
  // Base case: stops the recursion
  if (baseCondition) {
    return baseValue;
  }

  // Recursive case: function calls itself
  return recursiveFunction(smallerInput);
}

Every recursive function needs two parts:

  • Base case - The condition that stops the recursion
  • Recursive case - The function calling itself with a smaller input
Always Have a Base Case
Without a base case, your function will call itself forever until the call stack overflows and crashes.

Simple Example: Countdown

Let's start with a simple countdown function:

javascript
function countdown(n) {
  // Base case: stop when n reaches 0
  if (n <= 0) {
    console.log("Blastoff!");
    return;
  }

  // Current step
  console.log(n);

  // Recursive call with smaller value
  countdown(n - 1);
}

countdown(5);
// Output: 5, 4, 3, 2, 1, "Blastoff!"

Classic Example: Factorial

The factorial of n (written as n!) is the product of all positive integers up to n. This is a classic recursion example:

javascript
// Factorial: n! = n × (n-1) × (n-2) × ... × 1
// 5! = 5 × 4 × 3 × 2 × 1 = 120

function factorial(n) {
  // Base case: 0! = 1, 1! = 1
  if (n <= 1) {
    return 1;
  }

  // Recursive case: n! = n × (n-1)!
  return n * factorial(n - 1);
}

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

// How it works:
// factorial(5)
// = 5 * factorial(4)
// = 5 * 4 * factorial(3)
// = 5 * 4 * 3 * factorial(2)
// = 5 * 4 * 3 * 2 * factorial(1)
// = 5 * 4 * 3 * 2 * 1
// = 120

Fibonacci Sequence

The Fibonacci sequence is another classic recursion example where each number is the sum of the two before it:

javascript
// Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21...
// Each number is the sum of the two preceding ones

function fibonacci(n) {
  // Base cases
  if (n === 0) return 0;
  if (n === 1) return 1;

  // Recursive case: fib(n) = fib(n-1) + fib(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(6));  // 8
console.log(fibonacci(10)); // 55

// Note: This simple version is inefficient for large n
// because it recalculates the same values many times
Performance Note
This simple Fibonacci implementation is inefficient because it recalculates the same values many times. See the memoization section for an optimized version.

Recursion with Arrays

Recursion works well for processing arrays by handling one element at a time:

javascript
// Sum all numbers in an array
function sumArray(arr) {
  // Base case: empty array
  if (arr.length === 0) {
    return 0;
  }

  // Recursive case: first element + sum of rest
  return arr[0] + sumArray(arr.slice(1));
}

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

// Find maximum value in array
function findMax(arr) {
  // Base case: single element
  if (arr.length === 1) {
    return arr[0];
  }

  // Compare first with max of rest
  const maxOfRest = findMax(arr.slice(1));
  return arr[0] > maxOfRest ? arr[0] : maxOfRest;
}

console.log(findMax([3, 7, 2, 9, 1])); // 9

Nested Data Structures

Recursion really shines when working with nested or tree-like structures:

javascript
// Recursion shines with nested structures

const fileSystem = {
  name: "root",
  children: [
    { name: "file1.txt" },
    {
      name: "folder1",
      children: [
        { name: "file2.txt" },
        { name: "file3.txt" }
      ]
    },
    {
      name: "folder2",
      children: [
        { name: "file4.txt" },
        {
          name: "subfolder",
          children: [
            { name: "file5.txt" }
          ]
        }
      ]
    }
  ]
};

// Find all file names recursively
function getAllFiles(node) {
  // Base case: no children (it's a file)
  if (!node.children) {
    return [node.name];
  }

  // Recursive case: collect files from all children
  let files = [];
  for (const child of node.children) {
    files = files.concat(getAllFiles(child));
  }
  return files;
}

console.log(getAllFiles(fileSystem));
// ["file1.txt", "file2.txt", "file3.txt", "file4.txt", "file5.txt"]

Deep Clone Example

javascript
// Deep clone an object (handles nested objects)
function deepClone(obj) {
  // Base case: primitives and null
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }

  // Handle arrays
  if (Array.isArray(obj)) {
    return obj.map(item => deepClone(item));
  }

  // Handle objects
  const cloned = {};
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloned[key] = deepClone(obj[key]);
    }
  }
  return cloned;
}

const original = {
  name: "Alice",
  address: {
    city: "NYC",
    coords: { lat: 40.7, lng: -74 }
  },
  hobbies: ["reading", "coding"]
};

const clone = deepClone(original);
clone.address.city = "LA"; // Doesn't affect original
console.log(original.address.city); // "NYC"

Avoiding Stack Overflow

Each recursive call adds a frame to the call stack. Too many calls cause a stack overflow error:

javascript
// Without a base case = infinite recursion = crash!

function badRecursion(n) {
  // Missing base case!
  return badRecursion(n - 1);
}

// badRecursion(5); // RangeError: Maximum call stack size exceeded

// Always ensure your base case is reachable
function safeRecursion(n) {
  console.log("n =", n);

  // Base case: MUST be reachable
  if (n <= 0) {
    return "Done!";
  }

  // Make sure we move toward base case
  return safeRecursion(n - 1); // n decreases each time
}
Preventing Stack Overflow
  • Always have a reachable base case
  • Ensure each call moves toward the base case
  • Consider iteration for very deep recursion
  • Use tail recursion or trampolining for optimization

Recursion vs Iteration

Any recursive function can be written iteratively, and vice versa. Here's the same factorial function both ways:

javascript
// Factorial: Recursion vs Iteration

// Recursive version
function factorialRecursive(n) {
  if (n <= 1) return 1;
  return n * factorialRecursive(n - 1);
}

// Iterative version
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

// Both produce the same result
console.log(factorialRecursive(5)); // 120
console.log(factorialIterative(5)); // 120

// Iterative is more memory-efficient
// Recursive is often more readable for complex problems
AspectRecursionIteration (Loops)
ReadabilityOften cleaner for complex problemsSimpler for basic tasks
Memory usageUses call stack (more memory)Constant memory
PerformanceCan be slower (function calls)Generally faster
Best forTrees, nested data, divide & conquerLinear sequences, simple counting
RiskStack overflow if too deepInfinite loop if no exit

Tail Recursion

Tail recursion is when the recursive call is the last operation in the function. This can theoretically be optimized to prevent stack overflow:

javascript
// Tail recursion: recursive call is the LAST operation

// NOT tail recursive (multiplication after recursive call)
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // Has to multiply after return
}

// Tail recursive version (uses accumulator)
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Last operation
}

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

// Tail recursion can theoretically be optimized
// to reuse stack frames, but most JS engines don't do this
Browser Support
While ES6 specifies tail call optimization (TCO), most browsers don't implement it. Safari is the only major browser with TCO support.

Memoization (Optimization)

Memoization caches results to avoid redundant calculations. It dramatically improves performance for functions that are called with the same arguments:

javascript
// Fibonacci with memoization (caching)

// Slow: recalculates same values many times
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// Fast: caches results
function fibFast(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;

  memo[n] = fibFast(n - 1, memo) + fibFast(n - 2, memo);
  return memo[n];
}

console.time("Slow");
console.log(fibSlow(30)); // Takes a while...
console.timeEnd("Slow");

console.time("Fast");
console.log(fibFast(30)); // Almost instant!
console.timeEnd("Fast");

When to Use Recursion

Good Use Cases

  • Tree traversal (DOM, file systems, JSON)
  • Nested data processing
  • Divide and conquer algorithms (quicksort, mergesort)
  • Mathematical sequences (factorial, Fibonacci)
  • Backtracking problems (sudoku solver, maze solver)

Consider Iteration Instead When

  • Simple counting or iteration over arrays
  • Performance is critical
  • Recursion depth could be very large
  • Memory usage is a concern

Test Your Knowledge

JavaScript Recursion Quiz

5 questions
Question 1

What is a base case in recursion?

Question 2

What happens if a recursive function has no base case?

Question 3

What is the result of factorial(0)?

Question 4

When is recursion typically better than iteration?

Question 5

What is memoization?

Coding Challenge

Flatten Nested Arrays
Medium

Write a recursive function that takes a nested array of any depth and returns a flat array with all elements.

Starter Code
// Challenge: Implement a recursive function to flatten a nested array
// Example: [1, [2, [3, 4], 5], 6] should become [1, 2, 3, 4, 5, 6]

function flatten(arr) {
  // Your code here
  // Hint: Check if each element is an array
  // If it is, recursively flatten it
  // If not, add it to the result
}

// Test cases
console.log(flatten([1, 2, 3]));
// Expected: [1, 2, 3]

console.log(flatten([1, [2, 3], 4]));
// Expected: [1, 2, 3, 4]

console.log(flatten([1, [2, [3, [4, 5]]]]));
// Expected: [1, 2, 3, 4, 5]

console.log(flatten([[[[1]]], [[2]], [3], 4]));
// Expected: [1, 2, 3, 4]

Summary

  • Recursion is when a function calls itself to solve smaller instances of a problem
  • Every recursive function needs a base case to stop and a recursive case to continue
  • Recursion excels at tree-like structures and nested data
  • Watch out for stack overflow - always ensure the base case is reachable
  • Memoization can dramatically improve recursive function performance
  • Choose recursion for elegance with complex structures, iteration for performance with simple sequences
PreviousJavaScript HoistingNextJavaScript Objects

Tutorials

JavaScript