Recursion in DSA: A Beginner-Friendly Introduction

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem becomes so small it can be answered directly. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that shrinks the problem and calls itself again. Master recursion and you unlock trees, graphs, backtracking, and divide-and-conquer — whole families of algorithms become natural.

A first example: factorial

The factorial of n (written n!) is n × (n-1) × ... × 1. Notice the self-similarity: n! = n × (n-1)!. That single observation is the recursion. The base case is 0! = 1.

long long factorial(int n) {
    if (n <= 1) return 1;        // base case
    return n * factorial(n - 1); // recursive case
}

long factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

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

def factorial(n):
    if n <= 1:
        return 1                 # base case
    return n * factorial(n - 1)  # recursive case

Calling factorial(4) unfolds as 4 × factorial(3) → 4 × 3 × factorial(2) → 4 × 3 × 2 × factorial(1) → 4 × 3 × 2 × 1 = 24.

The two ingredients every recursion needs

1. Base case — the smallest input you can answer without recursing. Without it, the function calls itself forever and crashes.
2. Recursive case — reduce the problem toward the base case, then combine. If each call doesn’t get closer to the base case, you have an infinite recursion.

For beginners: Read a recursive function with faith, not by tracing every call. Trust that factorial(n - 1) returns the right answer for the smaller problem, then ask only: “given that, how do I build my answer?” This leap of faith is the key mental shift. The page on the call stack shows what really happens underneath.

Why recursion is worth learning

Some structures are defined recursively, so recursive code mirrors them exactly:

• A list is an element followed by a smaller list.
• A tree is a node whose children are smaller trees — see tree traversals.
• Many problems split into smaller copies of themselves — see divide and conquer.

Here is summing an array recursively — define the sum of a[i..] as a[i] plus the sum of a[i+1..]:

int sumFrom(const std::vector<int>& a, int i) {
    if (i == (int)a.size()) return 0;   // empty tail
    return a[i] + sumFrom(a, i + 1);
}

int sumFrom(int[] a, int i) {
    if (i == a.length) return 0;        // empty tail
    return a[i] + sumFrom(a, i + 1);
}

function sumFrom(a, i) {
  if (i === a.length) return 0;         // empty tail
  return a[i] + sumFrom(a, i + 1);
}

def sum_from(a, i):
    if i == len(a):
        return 0                # empty tail
    return a[i] + sum_from(a, i + 1)

Complexity at a glance

A recursive function’s cost is “work per call × number of calls.” factorial makes n calls doing O(1) work each → O(n) time. It also uses O(n) space because n calls are paused on the call stack at once — a cost iteration avoids.

Going deeper: Recursion is not free. Each call has overhead and stack space, and naive recursion can repeat work exponentially (the classic recursive Fibonacci is O(2ⁿ)). When that bites, you reach for memoization or rewrite it as a loop.

What’s next

• How recursion works — the call stack, frame by frame.
• Base & recursive cases — designing them correctly.
• Recursion vs iteration — when to pick which.

When you’re ready, test yourself with the recursion exercises.