Recursion

In simple words

Recursion is a function that calls itself on a smaller version of the same problem. Every recursive function has two parts:

1. Base case — the smallest input where you already know the answer (stop here).
2. Recursive case — break the problem into a smaller piece, call yourself, and combine the result.

The trick is to trust that the smaller call works, just like you trust a library method.

Key ideas

• Each call is stored on the call stack. Too deep (roughly 10,000+ in default Java) → StackOverflowError.
• Draw the recursion tree to find complexity: (number of calls) × (work per call).
• Naive Fibonacci makes ~2ⁿ calls because it solves the same subproblem again and again → fix with memoization (store answers). This is the doorway to Dynamic Programming.
• Java does not optimize tail recursion; convert very deep recursion to a loop or an explicit stack.
• Recursion is the backbone of trees, graphs (DFS), backtracking, divide & conquer, and DP.

Operations & cost

Java code

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

// Fibonacci with memoization: O(n) instead of O(2^n)
long[] memo = new long[100];
long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

// Fast power: x^n in O(log n)
double myPow(double x, long n) {
    if (n == 0) return 1;
    if (n < 0) return 1 / myPow(x, -n);
    double half = myPow(x, n / 2);
    return (n % 2 == 0) ? half * half : half * half * x;
}

Spot it when

• The problem is defined in terms of itself (tree, nested structure, 'for each choice…').
• You can say: 'if I knew the answer for n-1, I could get n'.

Practice problems

Interview tip

★ On the whiteboard, draw the recursion tree for n = 3 or 4. It makes the complexity obvious and shows the interviewer how you think.