Overview

Recursion is a technique in which a function calls itself. Although it can feel unfamiliar at first, recursion is a powerful way to solve problems involving trees, graphs, divide and conquer, and backtracking.

Key concepts

• The base case stops further recursive calls
• The recursive case calls the function with a smaller or simpler input
• Every call must make progress toward the base case
• Missing or unreachable base cases can cause a stack overflow

What is Recursion?

Recursion breaks a problem into smaller instances of the same problem. The function continues calling itself until it reaches a condition it can solve directly, known as the base case.

The two essential parts

• Base case: stops the recursive process
• Recursive case: calls the function again with a smaller or simpler input

Without a valid base case, recursive calls continue until the program exhausts the call stack and fails.

Real-life examples

Imagine walking down a staircase one step at a time. Each step is a recursive call, and reaching the ground floor is the base case. Nested gift boxes work similarly: keep opening the next box until the smallest box contains no other box.

How Recursion works

This function counts down by reducing n by one on every call.

function countdown(n) {
  if (n === 0) {
    return;
  }

  console.log(n);
  countdown(n - 1);
}

countdown(5);
// 5, 4, 3, 2, 1

Call flow

• Start with n equal to 5
• Print 5 and call countdown(4)
• Continue with smaller values
• When n reaches 0, return without another call
• Complete the waiting calls in reverse order

Factorial using Recursion

The factorial of n is the product of all positive integers from 1 through n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.

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

  return n * factorial(n - 1);
}

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

Each factorial call waits for the smaller call to return. Once factorial(1) returns 1, the waiting multiplications complete in reverse order.

The Call Stack

The call stack stores information about active functions. Each recursive call is pushed onto the stack. After reaching the base case, calls return and are removed one by one until the stack is empty.

factorial(5)
  factorial(4)
    factorial(3)
      factorial(2)
        factorial(1) → 1
      returns 2
    returns 6
  returns 24
returns 120

Advantages of Recursion

• Makes naturally recursive problems easier to express
• Can produce concise and readable solutions
• Works naturally with trees and graphs
• Supports divide-and-conquer algorithms such as Merge Sort and Quick Sort
• Simplifies problems composed of similar subproblems

Limitations of Recursion

• Every call consumes call-stack memory
• Deep recursion can cause a stack overflow
• Function-call overhead can make recursion slower than iteration
• Recursive flow may initially be harder to trace

Recursion vs Iteration

Both approaches are valuable. Choose the one that most clearly and safely matches the problem and its constraints.

Where is Recursion used?

• Tree traversal
• Graph traversal
• Binary Search
• Merge Sort
• Quick Sort
• Backtracking
• File and folder navigation
• Factorial and Fibonacci calculations

Tips for beginners

• Identify the base case before writing the recursive call
• Define how each call makes the input smaller
• Draw the call stack or a recursion tree
• Practice countdown, factorial, and Fibonacci
• Trace small inputs by hand before running the code

Key takeaways

• A recursive function calls itself
• The base case stops recursion
• The recursive case reduces the problem
• The call stack stores active recursive calls
• Recursion is common in trees, graphs, sorting, and backtracking
• Recursive code may be elegant but generally uses more memory than iteration