Recursion Types

Recursion types classify a function's self-call structure — how many times it calls itself, in what shape, and where the call sits relative to other work — because that structure directly determines the recursion tree's shape, and the tree's shape directly determines time and space complexity.

Recognize the pattern

• Problem naturally splits into one smaller subproblem of the same kind ("do this, then recurse on the rest") → linear recursion.
• The recursive call is the very last statement, with nothing left to do after it returns → tail recursion.
• Problem splits into two independent subproblems that must both be solved before combining (divide-and-conquer, tree left/right children) → binary recursion.
• A function calls itself more than twice, or a variable number of times (one call per child, one per neighbor) → multiple/tree recursion.
• Two or more functions call each other in a cycle (A calls B, B calls A) → mutual (indirect) recursion.
• A recursive call appears inside the arguments of another recursive call, e.g. f(f(n-1)) → nested recursion.

Brute force vs optimal, per type

For linear recursion (e.g. factorial), there is no "brute force vs optimal" split at the recursion-structure level — the naive recursive form already visits each subproblem once. The real brute-force-vs-optimal question shows up in binary/tree recursion: naive Fibonacci recomputes overlapping subproblems (exponential blow-up), while memoized or bottom-up (dynamic programming) versions collapse the same recursion tree into linear work by caching results. Tail recursion is an optimization axis orthogonal to shape: a linear-recursive function rewritten so the recursive call is last lets a compiler (in languages with tail-call optimization — not standard Java/JVM) reuse one stack frame instead of growing the stack.

Complexity from first principles

Linear recursion — T(n) = T(n-1) + O(1). Unrolling: T(n) = T(n-1)+c = T(n-2)+2c = ... = T(0)+nc → O(n) time. Each call adds one stack frame that isn't popped until the base case returns, so O(n) space on the call stack (tail recursion doesn't change this on the JVM, since Java performs no TCO).

Binary recursion, non-overlapping (e.g. merge sort) — T(n) = 2T(n/2) + O(n). By the Master Theorem (a=2, b=2, f(n)=O(n) matches n^(log_b a)=n^1) → O(n log n) time. Recursion depth is log n, so O(log n) space for the call stack alone (merge sort's O(n) auxiliary array is separate).

Binary recursion, overlapping (naive Fibonacci) — T(n) = T(n-1) + T(n-2) + O(1), whose solution grows like φ^n (φ≈1.618) → Θ(φ^n) time (O(2^n) is only the quick loose upper bound), because the tree has Θ(φ^n) nodes with massive overlap: fib(3) is recomputed inside both fib(5)'s and independently inside fib(4)'s subtree. Depth is n, so O(n) space.

Traced worked example

Trace fib(5) with naive binary recursion, showing call count growth:

Calls grow by a factor of φ≈1.618 per step (15/9≈1.67, 9/5=1.8 — Θ(φ^n) growth, loosely bounded by 2^n) rather than growing linearly — the signature of overlapping binary recursion. With memoization (cache keyed by n), total calls collapse to O(n): each n from 0 to 5 is computed exactly once.

Java — three recursion shapes side by side

// Linear recursion: one call, one smaller subproblem
static long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Tail recursion: recursive call is the last operation, uses an accumulator
static long factorialTail(int n, long acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc); // nothing left to do after this call
}

// Binary recursion, overlapping: two calls, exponential without memoization
static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// Binary recursion, memoized: same shape, linear cost
static long fibMemo(int n, long[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

Go — mutual recursion example

// Mutual recursion: isEven and isOdd call each other
func isEven(n int) bool {
    if n == 0 {
        return true
    }
    return isOdd(n - 1)
}

func isOdd(n int) bool {
    if n == 0 {
        return false
    }
    return isEven(n - 1)
}

Pitfalls

• Assuming Java optimizes tail calls. Unlike Scheme or Scala's @tailrec, the JVM does not perform tail-call elimination — a "tail-recursive" Java function still grows the stack by n frames and can StackOverflowError for large n.
• Missing or wrong base case in binary/tree recursion causes runaway branching (infinite recursion or a StackOverflowError) much faster than in linear recursion, since each faulty level multiplies calls.
• Ignoring overlap in binary recursion. Writing naive Fibonacci-style code for a problem with overlapping subproblems (e.g. naive recursive coin-change or LCS) silently produces exponential runtime that only manifests at larger n in testing.
• Mutual recursion without a shared/decreasing measure — if neither function strictly reduces some quantity toward a base case, the pair can recurse forever.

When to use / when not — trade-offs

Use linear recursion when a problem reduces to one smaller identical subproblem (list/array processing) — it mirrors an iterative loop but reads more declaratively; prefer the equivalent iterative loop instead when n can be large, since the loop is O(1) space versus recursion's O(n) stack space, with no readability loss for simple accumulation.

Use binary/tree recursion when the problem is genuinely divide-and-conquer with non-overlapping subproblems (merge sort, tree traversal) — it is the natural and often optimal expression. When subproblems overlap (Fibonacci-like), pair it with memoization (top-down DP) or switch to iterative dynamic programming (bottom-up) — DP trades the elegance of pure recursion for guaranteed polynomial time and, in the iterative bottom-up form, O(1) or O(n) space instead of O(n) recursion stack plus memo table.

Takeaways

• The number and placement of recursive calls (one/last/two/many/cyclic) is what defines the recursion type — and it directly sets the shape of the recursion tree.
• Tree shape determines complexity: linear chains give O(n), balanced non-overlapping binary splits give O(n log n), and overlapping binary splits give exponential blowup unless memoized.
• Tail recursion is a stylistic/potential-optimization property, not a magic performance fix in Java — the JVM still pays O(n) stack space.
• Overlapping subproblems are the tell that a recursion needs memoization or a DP rewrite, not just "more recursion."

Recall: Why does naive recursive Fibonacci take exponential time while merge sort's binary recursion takes O(n log n), even though both make two recursive calls per invocation?

Sourced from CS recursion pedagogy (CLRS divide-and-conquer chapter, Master Theorem) and standard algorithms references on recursion trees and memoization.