Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Recursion Basics

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem.

Every recursive function needs two parts:

  1. Base case — the smallest input, answered directly (stops the recursion).
  2. Recursive case — break the problem into a smaller one and call yourself.
int factorial(int n) {
    if (n <= 1) return 1;            // base case
    return n * factorial(n - 1);     // recursive case: smaller problem
}

What happens in memory (the call stack)

Each call gets its own stack frame with its parameters and local variables. Calls pile up until the base case, then return one by one:

factorial(4)
 └ 4 * factorial(3)
        └ 3 * factorial(2)
               └ 2 * factorial(1)  → 1      (base case)
               ← 2 * 1 = 2
        ← 3 * 2 = 6
 ← 4 * 6 = 24

Too many frames (very deep recursion or a missing base case) → stack overflow.

How to think recursively (the "leap of faith")

  1. Decide what the function returns for input n.
  2. Assume it already works for smaller inputs.
  3. Use that answer to build the answer for n.
  4. Write the base case for the smallest input.

Example — sum of digits: sum(1234) = 4 + sum(123); base case sum(0) = 0.

def digit_sum(n):
    return 0 if n == 0 else n % 10 + digit_sum(n // 10)

Classic examples

Power in O(log n) (fast exponentiation):

long long power(long long x, int n) {
    if (n == 0) return 1;
    long long half = power(x, n / 2);       // solve the half once, reuse it
    return n % 2 ? half * half * x : half * half;
}

Reverse a string: rev(s) = rev(s[1:]) + s[0].

Palindrome check: first and last characters equal, and the middle is a palindrome.

Print 1 to n (work after the call → printed in increasing order):

void print(int n) {
    if (n == 0) return;
    print(n - 1);
    cout << n << ' ';
}

Move the cout before the call and it prints n down to 1.

Tower of Hanoi: move n−1 discs to the helper peg, move the largest, move n−1 on top → 2ⁿ − 1 moves.

def hanoi(n, src, dst, via):
    if n == 0: return
    hanoi(n - 1, src, via, dst)
    print(f"move disc {n} {src} → {dst}")
    hanoi(n - 1, via, dst, src)

Types of recursion

Type Meaning Example
Head recursion recursive call first, work after print 1..n above
Tail recursion the recursive call is the last thing done factorial with an accumulator
Tree recursion more than one recursive call Fibonacci, subsets
Indirect A calls B, B calls A is_even / is_odd

Tail recursion with an accumulator:

int fact(int n, int acc = 1) { return n <= 1 ? acc : fact(n - 1, acc * n); }

(C++ compilers may optimise it into a loop; Java and Python don't.)

Complexity of recursion

Time = number of calls × work per call. Space = maximum depth (the stack).

Function Calls Time Space
factorial(n) n O(n) O(n)
power(x, n) fast log n O(log n) O(log n)
naive fib(n) ~2ⁿ O(2ⁿ) O(n)
subsets of n items 2ⁿ O(n·2ⁿ) O(n)

Draw the recursion tree to count calls.

Memoization: when the same subproblems repeat

Naive fib(5) computes fib(3) twice and fib(2) three times. Store answers:

long[] memo = new long[n + 1];   // filled with -1
long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

O(2ⁿ) → O(n). This is top-down dynamic programming (Dynamic Programming).

Recursion with arrays: pass an index, not a copy

def array_sum(a, i=0):
    return 0 if i == len(a) else a[i] + array_sum(a, i + 1)

Slicing (a[1:]) copies the list each time → O(n²) for no reason.

Recursion vs iteration

Recursion Iteration
Code shorter for trees, backtracking, divide & conquer better for simple loops
Memory uses the call stack O(1) extra
Risk stack overflow when deep none

Python's default recursion limit is about 1000 — use iteration (or sys.setrecursionlimit carefully) for deep inputs.

Common mistakes

Practice

Recursion & Backtracking problems. Try: factorial, power, palindrome, sum of digits, print all subsets, permutations, N-Queens.

Interview one-liners

More DSA notes