Interview OS
Back to Coding Prep

Coding

Recursion

Solve a problem in terms of a smaller version of itself.

Coding pattern

Overview

Recursion expresses a problem in terms of smaller instances of itself. Getting it right means a correct base case, trusting the recursive call, and being aware of the call-stack depth so you know when to convert to iteration.

How it works

Coding pattern
BaseSplitCombineOutputBase casen==0Subproblemf(n−1)Merge+Result
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Base case

    • Define the stopping condition.
  2. 2

    Subproblem

    • Reduce to smaller inputs.
  3. 3

    Merge

    • Assemble the sub-answers.
  4. 4

    Result

    • Return the combined value.
    • Example: Factorial, tree walk

When to reach for it

  • Divide and conquer
  • Tree/graph traversal
  • Generating combinations

Example problem

Compute n! recursively.

Approach

  • Define the base case
  • Reduce toward it each call

Solution

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

Complexity

Time O(n), Space O(n) call stack.

Common pitfalls

  • Missing base case
  • Deep recursion blowing the stack

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions