Unit 3: Recursion and Advanced Techniques

I. Orientation

Recursion is a problem-solving technique in which a function solves an instance by calling itself on smaller or simpler instances. It depends on mathematical induction: establish a directly solvable base case, then reduce every larger case toward it.

• Defining properties:
  • Self-reference: A recursive function invokes itself directly or through another function.
  • Base condition: At least one input is solved without another recursive call.
  • Recursive reduction: Each call must move measurably toward a base case.
  • Call stack: Active calls retain parameters, local variables, and return addresses.
  • Correctness: The base case and reduction together support an inductive proof.
  • Complexity: Time depends on the number of calls; space depends mainly on maximum recursion depth.
  • Advanced use: Backtracking adds decision-making, constraint checking, and reversal of choices.

II. Foundations of Recursive Problem Solving

A. Introduction to recursion

Recursion expresses a solution in terms of smaller instances of the same problem.

• General structure: A function first checks a terminating case and otherwise performs a recursive reduction.

solve(x):
    if base_condition(x):
        return direct_answer
    return combine(x, solve(smaller(x)))

• Example: Factorial follows (n! = n(n-1)!), with (0! = 1).

long long factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

• Call sequence: factorial(3) creates calls for 3, 2, 1, and 0; results return as (1, 1, 2, 6).
• Typical domains: Trees, divide-and-conquer algorithms, combinatorial generation, depth-first search, and recurrence-defined sequences naturally support recursion.

B. Base condition

The base condition identifies an instance that can be answered immediately and stops further calls.

• Termination role: In factorial, n == 0 prevents the sequence (n,n-1,n-2,\ldots) from continuing indefinitely.
• Reachability requirement: The recursive step must approach the condition; calling factorial(n + 1) would move away from n == 0.
• Multiple bases: Fibonacci commonly uses both (F(0)=0) and (F(1)=1).
• Invalid inputs: A robust function may separately reject unsupported values such as negative factorial arguments.
• Failure consequence: A missing or unreachable base case causes unbounded call growth and eventually stack overflow.

C. Solving problems using recursion

A recursive solution is designed by defining the smaller subproblem before writing implementation details.

• Problem decomposition:
  • State: Record information describing one subproblem, such as an array index or tree node.
  • Choice: Determine which recursive calls can follow from that state.
  • Reduction: Make each call operate on less remaining work.
  • Combination: Merge returned values when the problem requires aggregation.
• Correctness method: Prove the base cases directly, assume smaller instances are solved correctly, and show that the recurrence produces the current answer.
• Complexity equation: Binary search satisfies (T(n)=T(n/2)+O(1)), giving (T(n)=O(\log n)).
• Memoization: Caching repeated states converts naive Fibonacci from (O(2^n)) time to (O(n)) time.

D. Classic and Modern Approaches

Recursive techniques range from direct mathematical definitions to optimized state-space algorithms.

1. Classic approaches: Factorial, Euclid’s algorithm, binary search, merge sort, tree traversal, and Tower of Hanoi closely mirror recurrence relations.
2. Modern approaches: Memoized dynamic programming, branch-and-bound, constraint propagation, recursive descent parsing, and recursive search with bitmasks reduce repeated or impossible work.

• Optimization principle: Preserve recursive clarity while controlling branching, repeated states, and stack depth.
• Competitive coding practice: Recursive depth-first search is often paired with arrays or bitmasks for (O(1)) state checks.

III. Forms of Recursion

A. Direct vs. Indirect Recursion

Recursion is classified by whether a function returns to itself immediately or through other functions.

1. Direct recursion: Function f calls f.

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

2. Indirect recursion: Function f calls g, and g eventually calls f.

bool isEven(int n);
bool isOdd(int n) {
    return n == 0 ? false : isEven(n - 1);
}
bool isEven(int n) {
    return n == 0 ? true : isOdd(n - 1);
}

• Call-cycle requirement: Every path in the cycle must collectively progress toward termination.
• Practical distinction: Indirect recursion appears in parsers and mutually dependent state transitions but is harder to trace.

B. Tailed vs. Non-Tailed Recursion

Tail recursion performs no pending computation after the recursive call returns.

1. Tailed recursion: The recursive call is the final operation.

long long factTail(int n, long long acc) {
    if (n == 0) return acc;
    return factTail(n - 1, acc * n);
}

2. Non-tailed recursion: Work remains after the call; return n * factorial(n - 1) must perform multiplication during unwinding.

• Stack implication: A compiler may optimize tail calls into iteration, but C++ does not guarantee this optimization.
• Conversion: Accumulator parameters often transform non-tail recursion into tail recursion.
• Algorithmic fit: Tree traversal is usually non-tail because execution must return to process other branches.

IV. Execution Cost and Evaluation

A. Memory Allocation in Recursion

Each unfinished call normally occupies a stack frame until it returns.

• Frame contents: Parameters, local variables, saved registers, return address, and bookkeeping data.
• Depth measure: Factorial has (O(n)) stack depth, while balanced binary search has (O(\log n)).
• Unwinding: When a base case returns, frames are removed in last-in, first-out order.
• Heap distinction: Dynamically allocated objects usually reside on the heap, although references or pointers to them may be stored in stack frames.
• Stack overflow: A depth near (10^5) may fail under typical contest limits; the exact threshold depends on frame size and platform.
• Mitigation: Use iteration, an explicit stack, shallower decomposition, or carefully bounded recursion.

B. Advantages & disadvantages of recursive programming

Recursive programming improves structural expression but introduces execution and reliability costs.

1. Advantages:
   • Natural representation: Tree DFS directly recurses on child nodes.
   • Concise code: Divide-and-conquer and backtracking avoid manual stack management.
   • Proof alignment: The implementation often matches an inductive definition.
   • Local state: Each call receives its own parameters and local variables.
2. Disadvantages:
   • Memory overhead: Depth (d) generally requires (O(d)) stack space.
   • Call overhead: Function invocation can be slower than a loop.
   • Repeated computation: Naive Fibonacci recomputes identical states.
   • Debugging difficulty: Deep or indirect call chains complicate tracing.
   • Failure risk: Excessive depth can terminate the program through stack overflow.

V. Backtracking and Constraint Search

A. Backtracking

Backtracking recursively constructs candidates and abandons partial solutions that cannot become valid complete solutions.

• Core cycle: Choose an option, modify state, recurse, and undo the modification.

search(state):
    if complete(state):
        record(state)
        return
    for choice in candidates(state):
        if valid(choice, state):
            apply(choice, state)
            search(state)
            undo(choice, state)

• Pruning: Rejecting an invalid prefix prevents exploration of every completion beneath it.
• State restoration: The undo step must exactly reverse apply; otherwise sibling branches inherit corrupted state.
• Complexity: Worst-case time is often exponential, such as (O(2^n)) for include/exclude decisions.

B. Permutations

Permutation generation uses backtracking to arrange every element exactly once.

• State: At depth pos, indices before pos are fixed and remaining indices are candidates.
• Swap method: Swap each candidate into pos, recurse for pos + 1, and swap back.
• Output count: (n) distinct elements have (n!) permutations, so output-sensitive time is (O(n\cdot n!)).
• Duplicate handling: Sort the input and skip equal unused choices at the same recursion depth.
• Example: For {1,2,3}, fixing 1 produces {1,2,3} and {1,3,2} before the algorithm restores state and fixes 2.

C. Combination Sum

Combination Sum searches for number selections whose total equals a target.

• State definition: Use (index, remainingTarget, currentCombination) to represent one subproblem.
• Reuse rule: If a selected number may be reused, recurse with the same index; otherwise recurse with index + 1.
• Base cases: Record a combination when remainingTarget == 0; stop when it becomes negative or candidates are exhausted.
• Duplicate control: Sorting and advancing indices in nondecreasing order prevents order-based duplicates such as [2,3] and [3,2].
• Pruning: With positive sorted candidates, stop considering values greater than the remaining target.

D. N-Queens

N-Queens places (N) queens on an (N\times N) board so no two attack each other.

• Recursive level: Place exactly one queen in each row, making the row number the recursion depth.
• Constraints: A position (r,c) is unsafe when its column c, main diagonal r-c, or anti-diagonal r+c is already occupied.
• State structures: Boolean arrays or bitmasks provide constant-time conflict tests.
• Backtracking step: Mark the three attacked sets, recurse to row r+1, then unmark them.
• Search cost: The rough upper bound is (O(N!)), although diagonal pruning removes many arrangements.

VI. Specialized Recursive Problems

A. Next happy number

The next happy number is the smallest integer greater than a given value whose repeated digit-square sum reaches (1).

• Transformation: For digits (d_i), compute (f(n)=\sum d_i^2); for example, (19\rightarrow82\rightarrow68\rightarrow100\rightarrow1).
• Cycle detection: A number is unhappy if a transformed value repeats; use a set or Floyd’s cycle-detection algorithm.
• Recursive test: Return true at n == 1; otherwise recurse on f(n) while tracking visited values.
• Next-number search: Test n + 1, n + 2, and so on until the happy-number predicate succeeds.
• Complexity: Each transformation reduces a large integer to at most (81k), where (k) is its digit count.

B. Sum string

A sum string can be partitioned into numbers where each number after the first two equals their sum.

• Search method: Try every valid split for the first and second numbers, then recursively verify the remaining suffix.
• Recurrence condition: If strings represent (a) and (b), the next characters must begin with the decimal representation of (a+b).
• Leading-zero rule: A multi-digit term cannot start with 0; the single number "0" remains valid.
• Large values: Perform addition directly on decimal strings when terms may exceed built-in integer limits.
• Progress condition: Each successful match consumes the next sum, so recursion must eventually reach the string’s end.

C. Water overflow

The water overflow problem models liquid poured into the top glass of a triangular arrangement.

• Capacity rule: Each glass holds one unit; any excess is divided equally between the two glasses below it.
• Transition: If glass (r,c) contains (x>1), pass ((x-1)/2) to (r+1,c) and (r+1,c+1).
• Stored amount: After distributing excess, the current glass contains min(1, x).
• Recursive interpretation: Water reaching a glass is contributed by its upper-left and upper-right parents.
• Complexity: Simulating through row (R) processes (1+2+\cdots+R=O(R^2)) glasses and uses (O(R^2)) storage, reducible to (O(R)) with row-wise arrays.