Recursive Design

Recursion expresses a problem in terms of smaller instances of itself. Used carefully, it mirrors recursive definitions, traverses hierarchical structures, and supports divide-and-conquer algorithms. Used carelessly, it hides repeated work, nontermination, excessive stack depth, or an exponential search tree. This chapter develops recursive decomposition together with the proofs and recurrences needed to control it.

Recursive Decomposition

Every correct recursive function needs two ingredients:

1. A base case — an input simple enough to answer directly, without further recursion. This is what stops the recursion from going forever.
2. A recursive case — a way of expressing the answer to the current problem in terms of the answer to one or more smaller instances of the same problem.

The factorial recurrence provides a compact example. This C fragment assumes 0 <= n <= 20, the range whose exact result fits in unsigned long long on implementations with at least 64-bit values:

unsigned long long factorial(unsigned int n) {
    if (n <= 1) {
        return 1ULL;                    /* base case */
    }
    return n * factorial(n - 1U);       /* recursive case */
}

The recursive case directly implements n! = n(n-1)!. The base case implements 0! = 1 and stops descent. An iterative implementation instead maintains an accumulator invariant. The two forms compute the same recurrence but expose different proof structures.

Call Stack

Correctness, time, and space analysis require an accurate model of function calls.

Each active function call has a stack frame containing its parameters, local state, and return information. Frames follow last-in, first-out order on the call stack. A recursive call creates a new frame while the caller’s frame remains active.

For factorial(4), the stack reaches four frames before unwinding:

factorial(4) calls factorial(3)
  factorial(3) calls factorial(2)
    factorial(2) calls factorial(1)
      factorial(1) returns 1                  <- base case reached, stack stops growing
    factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

The trace exposes separate time and space costs:

• Time: the total work is the number of calls times the work per call — here, n calls each doing O(1) work outside the recursive call, giving O(n) overall.
• Space: up to n frames coexist at maximum depth, so auxiliary stack space is Theta(n) even without arrays or heap allocation.

For this numeric implementation, representation fails before stack depth becomes large: 21! exceeds a 64-bit unsigned long long. Other linear-depth recursions can reach stack limits when their values remain representable. A complete contract must therefore constrain both the mathematical input domain and the machine representation.

Tower of Hanoi

The Tower of Hanoi is a puzzle with three pegs (source A, auxiliary B, destination C) and n disks of different sizes stacked on peg A in decreasing order. The goal: move all disks to peg C, using peg B as scratch space, obeying one rule at all times — a larger disk may never rest on a smaller one.

Before the largest disk can move to C, the n-1 smaller disks must move from A to B. After the largest disk moves, the same subproblem moves those smaller disks from B to C. This yields two recursive calls on size n-1:

#include <stdio.h>

/* Precondition: n >= 0. */
void hanoi(int n, char from, char aux, char to) {
    if (n == 0) {
        return;                                  /* base case: nothing to move */
    }
    hanoi(n - 1, from, to, aux);                 /* move n-1 disks out of the way */
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, from, to);                 /* move n-1 disks onto the destination */
}

For hanoi(3, 'A', 'B', 'C'), the calls emit seven legal moves. The first recursive call clears the largest disk, and the second rebuilds the smaller stack above it.

The recurrence is T(n) = 2T(n-1) + 1, which solves to exactly 2^n - 1 moves and Theta(2^n) time. The move count is optimal: the largest disk requires one move, and at least 2^(n-1)-1 moves are necessary both to clear it and to rebuild above it. For n = 64, the count is approximately 1.8 * 10^19.

Hanoi has branching factor two and depth n, so its recursion tree has exponentially many nodes. Merge sort also branches twice but halves the input, giving depth Theta(log n) and Theta(n log n) work. Shrinking by one is not alone sufficient for exponential time—factorial makes one such call and is linear; exponential growth here comes from repeated branching across linear depth.

Ackermann Growth

The Ackermann function is a compact example of recursion whose depth and value grow far beyond ordinary primitive-recursive patterns:

/* Valid only while every result fits and recursion stays within stack limits. */
unsigned long long ackermann(unsigned m, unsigned long long n) {
    if (m == 0U) {
        return n + 1U;
    }
    if (n == 0U) {
        return ackermann(m - 1U, 1U);
    }
    return ackermann(m - 1U, ackermann(m, n - 1U));
}

Small closed forms already escalate:

A(0,n) = n+1
A(1,n) = n+2
A(2,n) = 2n+3
A(3,n) = 2^(n+3)-3

A(4,1)=65533; evaluating nearby inputs naively can exceed both integer range and call-stack capacity. The function is useful here as a boundary example, not as a practical numeric routine. A mathematically defined recursive function may be total over natural numbers while its direct C realization is unusable because finite integers and finite stacks violate the mathematical model.

Termination can be justified with lexicographic descent on (m,n) under an appropriate well-founded ordering: the inner A(m,n-1) decreases n, and the outer call then decreases m. A single numeric argument need not decrease at every syntactic call; the proof measure must match the nested structure.

Branching Recursion

factorial makes one recursive call per invocation and forms a linear chain. Naive recursive Fibonacci shows how multiple calls change the recursion tree. The fragment assumes 0 <= n <= 92, so the result fits in signed long long:

long long fib(int n) {
    if (n < 2) {
        return n;                           /* base cases: fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);         /* two recursive calls */
}

The call tree for fib(5) contains two calls to fib(3) and three calls to fib(2). Let C(n) be its total number of function calls. Then

Solving the recurrence gives C(n)=2F_{n+1}-1, where F_k is the kth Fibonacci number. Since F_k = Theta(phi^k) for phi=(1+sqrt(5))/2, the tight running time is Theta(phi^n). The frequently stated O(2^n) bound is a convenient but loose upper bound, not an exact doubling law. Only n + 1 distinct argument values exist; the rest of the exponential work is repeated computation.

The recursion has overlapping subproblems: different branches recompute the same fib(k). Memoization or bottom-up dynamic programming stores each distinct state and reduces the time to linear.

Recursive complexity depends on the number and size of generated calls, not the number of source lines. A compact branching recurrence can generate exponentially many invocations, while a longer function with one shrinking call can remain linear.

Divide and Conquer

Divide and conquer structures an algorithm in three stages:

1. Divide — split the problem into smaller sub-problems of the same kind.
2. Conquer — solve each sub-problem recursively (with a base case for the smallest instances).
3. Combine — merge the sub-solutions into a solution for the original problem.

Its benefit depends on the number and size of subproblems and on the cost of combining their answers. Two examples expose that difference.

Binary search divides a sorted array in half, recurses into the half that could contain the target, and needs no separate combine step because the subproblem’s answer is already the whole answer:

#include <stdbool.h>
#include <stddef.h>

static bool binary_search_range(const int arr[], size_t lo, size_t hi,
                                int target, size_t *out_index) {
    if (lo == hi) {
        return false;
    }

    size_t mid = lo + (hi - lo) / 2U;
    if (arr[mid] == target) {
        *out_index = mid;
        return true;
    }
    if (arr[mid] < target) {
        return binary_search_range(arr, mid + 1U, hi, target, out_index);
    }
    return binary_search_range(arr, lo, mid, target, out_index);
}

bool binary_search_recursive(const int arr[], size_t n, int target,
                             size_t *out_index) {
    if (out_index == NULL || (n > 0U && arr == NULL)) {
        return false;
    }
    return binary_search_range(arr, 0U, n, target, out_index);
}

The helper represents its candidate range as the half-open interval [lo,hi). It requires a non-decreasing array and valid readable storage for that interval. Both recursive branches strictly shorten the interval, mid + 1 never exceeds hi, and an empty range needs no negative sentinel. The compact Boolean interface uses false for both invalid input and absence; a status enum can distinguish them when callers need that information.

Merge sort divides an array into two halves, recursively sorts each half, and merges the two sorted halves in O(n) time. The Sorting chapter develops the merge operation and the complete algorithm.

void merge_sort(int arr[], int lo, int hi) {
    if (lo >= hi) {
        return;                                  /* base case: 0 or 1 elements, already sorted */
    }
    int mid = lo + (hi - lo) / 2;
    merge_sort(arr, lo, mid);                    /* conquer: sort left half */
    merge_sort(arr, mid + 1, hi);                /* conquer: sort right half */
    merge(arr, lo, mid, hi);                     /* combine: merge the two sorted halves */
}

Both functions halve the problem. Their combine costs differ: binary search does constant work at each level, while merge sort performs a linear merge. The recurrence analysis below turns that difference into Theta(log n) versus Theta(n log n).

Recurrences

To analyze a recursive algorithm’s running time, you write a recurrence relation — an equation that expresses T(n), the time to solve a problem of size n, in terms of T applied to smaller sizes, plus the cost of the non-recursive work at this level. Reading the divide-and-conquer recipe straight off the code gives you the recurrence almost for free:

• Binary search: one recursive call on a problem half the size, plus O(1) work to decide which half. T(n) = T(n/2) + O(1).
• Merge sort: two recursive calls, each on a problem half the size, plus O(n) work to merge. T(n) = 2T(n/2) + O(n).
• Naive Fibonacci: two recursive calls, each on a problem only one smaller (not half!), plus O(1) work to add. T(n) = T(n-1) + T(n-2) + O(1).

After writing a recurrence, solve it with a method whose assumptions match its shape.

Substitution Method

The substitution method guesses a bound and proves it by induction. For merge sort, guess T(n) <= c n log_2 n + d n for powers of two. Assuming it holds for n/2:

Choose c >= a, and the final term is nonpositive, completing the upper-bound step after checking a base case. A matching lower-bound induction yields Theta(n log n).

The guess usually comes from expansion or a recursion tree. Substitution turns that intuition into a proof. Include constants and lower-order slack: trying to prove an exact-looking inequality can fail even when the asymptotic guess is right.

Recursion Tree

Draw the recursion as a tree, where each node represents one call and is labeled with the amount of non-recursive work it does. Then sum the work level by level.

For merge sort, T(n) = 2T(n/2) + O(n): the root does O(n) work and has 2 children, each handling a problem of size n/2 and doing O(n/2) work — so each level of the tree does a total of O(n) work (two nodes doing n/2 each, four nodes doing n/4 each, and so on — it’s always n in total). The tree has O(log n) levels, because the problem size halves at each level until it reaches the base case. Total cost: (work per level) × (number of levels) = O(n) × O(log n) = O(n log n).

For binary search, T(n) = T(n/2) + O(1): there’s only one branch per level, doing O(1) work, and O(log n) levels. Total cost: O(1) × O(log n) = O(log n).

For Tower of Hanoi, T(n) = 2T(n - 1) + Theta(1). The tree has n levels, and level i has 2^i constant-work nodes. Summing the geometric series gives Theta(2^n).

Master Theorem

The Master Theorem solves many recurrences of the form T(n) = aT(n/b) + f(n), where a >= 1, b > 1, and f(n) is eventually nonnegative. The following common three-case version compares f(n) with n^(log_b a):

• If f(n) = O(n^(log_b a - epsilon)) for some epsilon > 0, the leaves dominate and T(n) = Theta(n^(log_b a)).
• If f(n) = Theta(n^(log_b a)), all levels have the same asymptotic work and T(n) = Theta(n^(log_b a) log n).
• If f(n) = Omega(n^(log_b a + epsilon)) for some epsilon > 0, and the regularity condition a f(n/b) <= c f(n) holds for some constant c < 1 and all sufficiently large n, the root-side work dominates and T(n) = Theta(f(n)).

For merge sort, a = 2, b = 2, and f(n) = Theta(n) = Theta(n^(log_2 2)), so case 2 gives Theta(n log n). For binary search, a = 1, b = 2, and f(n) = Theta(1) = Theta(n^(log_2 1)), so case 2 gives Theta(log n).

The other cases become clearer by comparing work across levels.

Leaf-dominated recurrence. Consider

Here n^(log_2 4)=n^2, while f(n)=n=O(n^(2-1)), so case 1 predicts Theta(n^2). At level i, there are 4^i subproblems of size n/2^i; their combined nonrecursive work is

It doubles toward the leaves. For n=16, level costs are 16,32,64,128,256; the bottom level dominates their geometric sum.

Root-dominated recurrence. Consider

The threshold is n^(log_2 2)=n, and n^2=Omega(n^(1+1)). The regularity check is

so c=1/2 satisfies case 3. Level i contributes n^2/2^i; for n=16, the costs are 256,128,64,32,16. Work decreases geometrically away from the root, giving Theta(n^2) total.

A near miss. The stated three-case theorem does not directly classify

The combine work is larger than the threshold n, but not by a polynomial factor n^epsilon, so case 3’s separation condition fails. A recursion tree still works. At level i, total combine work is

For n=16, these contributions are 64,48,32,16, followed by Theta(16) leaf work. Summing the descending arithmetic sequence over Theta(log n) levels yields Theta(n log^2 n). A theorem is a conditional tool, not permission to force every recurrence into its nearest-looking case.

The theorem does not cover every recurrence. Fibonacci’s T(n) = T(n-1) + T(n-2) + Theta(1) is not of the required equal-fraction form. A recursion tree can still organize such an analysis, but it is not an automatic solver: irregular subproblem sizes or level costs may require substitution, a more general theorem, or another argument.

Karatsuba Multiplication

Divide and conquer can improve an algorithm by reducing the number of recursive subproblems, not only their sizes. Let two n-digit nonnegative integers be split around m low digits in base B:

Direct expansion gives

A direct recursive implementation computes four half-size products: ac, ad, bc, and bd. That recurrence, T(n)=4T(n/2)+Theta(n), remains Theta(n^2). Karatsuba observes that the middle coefficient can be recovered from one different product:

It computes only

z2 = KARATSUBA(a,c)
z0 = KARATSUBA(b,d)
z1 = KARATSUBA(a+b,c+d) - z2 - z0
return z2 * B^(2m) + z1 * B^m + z0

For 1234 * 5678 with B=10 and m=2, the splits are a=12, b=34, c=56, and d=78:

z2 = 12 * 56 = 672
z0 = 34 * 78 = 2652
z1 = 46 * 134 - 672 - 2652 = 2840
result = 672 * 10^4 + 2840 * 10^2 + 2652
       = 7,006,652

Digit addition, subtraction, shifting, and carry normalization take Theta(n) work. The recurrence is therefore

and the Master Theorem gives Theta(n^(log_2 3)), approximately Theta(n^1.585). Removing one half-size multiplication changes the exponent.

A complete large-integer implementation must handle unequal lengths, leading zeros, signs, carry propagation, temporary buffers, allocation failure, and overlapping storage. It normally switches to schoolbook multiplication below a measured threshold because recursive allocation and extra additions dominate at small sizes. The algebra proves correctness; the digit representation and threshold determine whether the implementation is robust and fast.

Uneven Splits

Not every divide step creates equal fractions. Quicksort with a pivot that leaves k elements on one side has recurrence

If both sides are always bounded by a fixed fraction of n, recursion depth is Theta(log n) and each level performs Theta(n) partition work, giving Theta(n log n). If k=0 at every level, expansion gives

The equal-size Master Theorem does not apply directly because k depends on the pivot and the input. A recursion tree, substitution, or probabilistic analysis must describe that dependency. Stack depth follows the longest branch rather than total node count: a balanced split has logarithmic depth, while repeated extreme splits create linear depth. Recursing on the smaller partition and iterating over the larger one can cap call-stack depth without changing the partition work.

Maximum Subarray

Given an integer array, the maximum-subarray problem asks for a contiguous subarray with largest sum. In [-2,1,-3,4,-1,2,1,-5,4], subarray [4,-1,2,1] has the maximum sum 6.

The brute-force approach checks every possible subarray — O(n²) or O(n³) depending on how naively you compute the sums. Can divide and conquer do better? Split the array into a left half and a right half. The maximum subarray either:

1. lies entirely within the left half, or
2. lies entirely within the right half, or
3. straddles the midpoint — and this is the case that makes the problem interesting.

Cases 1 and 2 are solved by recursion — the same problem, on a half-sized input. Case 3 cannot be solved recursively, because a subarray that crosses the midpoint isn’t “entirely within” either recursive sub-problem; it has to be found directly. But it can be found in O(n) time with a small, sharp insight: any subarray crossing the midpoint consists of some suffix of the left half glued to some prefix of the right half — and the best such suffix and the best such prefix can each be found independently with a single linear scan outward from the midpoint, then added together.

The implementation scans outward once on each side. It requires a non-null array, 0 <= lo <= hi, and—when calling the helper—lo <= mid < hi. Every partial sum and the final combined sum must fit in int; a status-returning checked-arithmetic version is required when that contract cannot be guaranteed.

#include <limits.h>

/* Returns the maximum sum of a subarray that crosses index `mid`. */
int max_crossing_sum(const int arr[], int lo, int mid, int hi) {
    int left_sum = INT_MIN, sum = 0;
    for (int i = mid; i >= lo; i--) {            /* scan left, extending the suffix */
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    int right_sum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= hi; i++) {        /* scan right, extending the prefix */
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    return left_sum + right_sum;                 /* best suffix + best prefix, glued at mid */
}

int max_subarray_sum(const int arr[], int lo, int hi) {
    if (lo == hi) {
        return arr[lo];                           /* base case: one element */
    }
    int mid = lo + (hi - lo) / 2;
    int left  = max_subarray_sum(arr, lo, mid);
    int right = max_subarray_sum(arr, mid + 1, hi);
    int cross = max_crossing_sum(arr, lo, mid, hi);

    int best = (left > right) ? left : right;
    return (cross > best) ? cross : best;         /* take the best of all three cases */
}

The recurrence is T(n) = 2T(n/2) + Theta(n). A recursion tree has Theta(log n) levels and total crossing-scan work Theta(n) per level; equivalently, the Master Theorem applies with a=2, b=2, and f(n)=Theta(n). Both derivations give the tight bound Theta(n log n), improving on the direct Theta(n^2) enumeration of all start/end pairs.

At the top-level split of [-2,1,-3,4,-1,2,1,-5,4], mid=4:

The crossing scan accumulates leftward sums -1,3,0,1,-1, whose maximum is 3, and rightward sums 2,3,-2,2, whose maximum is also 3. Their sum produces [4,-1,2,1]. The three cases are exhaustive because every contiguous subarray is either wholly left, wholly right, or contains elements on both sides of the split. That case partition is the correctness argument for taking the maximum of the three recursive results.

Kadane’s dynamic-programming formulation solves the same problem in Theta(n) time with one scan. The divide-and-conquer solution remains a useful derivation and demonstrates that obtaining one correct improvement does not establish optimality.

Recursive Interfaces

A mathematical recurrence omits several decisions that a C interface must expose.

Empty instances. Half-open ranges [lo,hi) represent emptiness with lo==hi and avoid negative indices. Whether an empty maximum-subarray query is invalid, has sum zero, or returns an optional result is a specification decision; the nonempty recurrence cannot decide it for the caller.

Failure propagation. A recursive function that allocates memory or performs checked arithmetic needs more than the mathematical result type. If a child reports allocation failure, the parent must release any resources it owns and propagate that status without combining an invalid value. A Boolean result can distinguish success from failure; an enum can separate invalid input, allocation failure, numeric overflow, and ordinary absence.

Mutation boundaries. Merge sort mutates ranges that later need to be combined. If one child can fail after modifying its half, the function must state whether the caller receives a partially transformed array. Strong failure atomicity requires sorting into temporary storage or rolling changes back, which changes space and implementation cost.

Output volume. Hanoi prints inside recursion, coupling computation to stdout and making I/O failure invisible. A reusable interface can invoke a caller-supplied callback for each move and stop if the callback rejects further output. The algorithm still requires 2^n-1 successful emissions, but the caller controls storage, formatting, cancellation, and error handling.

Hidden state. Global counters and static scratch buffers shorten parameter lists but make reentrancy, concurrent calls, and proof invariants harder. Passing explicit context makes each frame’s dependencies visible. When scratch space is shared across children, the contract must state which range each child owns and when that space may be reused.

These interface choices do not alter the recurrence’s mathematical identity, but they determine whether the implementation remains correct under empty input, bounded arithmetic, failure, aliasing, and reuse.

Iterative Conversion

Tail-recursive functions whose recursive call is the final action can often be converted into a loop by replacing parameters with mutable state. Euclid’s algorithm illustrates the translation:

unsigned gcd_iterative(unsigned a, unsigned b) {
    while (b != 0U) {
        unsigned remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

For non-tail recursion, an iterative version needs an explicit stack frame containing every local value required after a child returns. Iterative DFS, tree traversal, and parser evaluation do not eliminate the logical stack; they move its representation into programmer-controlled memory. This can avoid a fixed call-stack limit and permit pausing or inspecting the computation, at the cost of more bookkeeping.

Stack-Depth Analysis

Time counts all calls; stack space counts the maximum number of calls alive simultaneously.

• Factorial makes Theta(n) calls and reaches depth Theta(n).
• Naive Fibonacci makes exponentially many calls but reaches depth only Theta(n).
• Balanced merge sort makes Theta(n) total calls and reaches depth Theta(log n).
• Quicksort can reach depth Theta(n) under poor partitions even when its average depth is logarithmic.

Evaluate stack depth independently from total work. In C, tail-call elimination is not guaranteed, so a tail-recursive source function should not be assumed to use constant stack space. Convert explicitly when depth can grow beyond safe environmental limits.

Recursive Complexity

For every recursive algorithm, record:

1. number of recursive calls made per state;
2. size of each child state;
3. nonrecursive work performed at the state;
4. maximum root-to-leaf depth;
5. whether different branches repeat the same subproblem;
6. space occupied per live frame and by auxiliary buffers.

These facts determine the recurrence and stack bound. A short implementation may be exponential; a branching implementation may still be linear when subproblems partition a tree’s nodes; and an asymptotically efficient algorithm may remain unsafe if its recursion becomes input-depth linear.

Recursion Review

• Recursive design requires complete base cases and recursive calls that decrease under a well-founded measure.
• Call count determines time, while maximum live depth determines call-stack space.
• Divide and conquer separates division, recursive solution, and combination.
• Recurrences translate source structure into cost equations; substitution, recursion trees, and the Master Theorem solve common forms.
• Tower of Hanoi shows exponential branching under decrement-by-one shrinkage; Ackermann illustrates extreme nested recursive growth.
• Maximum subarray demonstrates a linear combine step producing an O(n log n) divide-and-conquer solution.
• Explicit stacks and loops can replace recursion when depth or control requirements demand it.

Recursion Problems

Call Trees

1. Trace factorial(5) through descent and return. At each point record the live frames, completed multiplications, and maximum stack depth.
2. Draw every call made by fib(6). Verify the formula C(n)=2F_{n+1}-1, count repeated argument values, and compare total calls with the seven distinct states 0..6.
3. List the seven moves for hanoi(3), then derive the exact number of moves and maximum live depth for hanoi(n).
4. Evaluate only the calls needed for A(2,2). Mark which syntactic calls decrease n, which decrease m, and how the lexicographic termination measure handles both.

Recurrence Derivations

5. Solve each recurrence tightly and identify an applicable method: T(n)=T(n/2)+n, T(n)=3T(n/2)+n, T(n)=8T(n/2)+n^2, and T(n)=T(n-1)+n.
6. For T(n)=4T(n/2)+n, compute every level cost at n=32, sum them exactly under base cost T(1)=1, and compare with the asymptotic result.
7. Prove T(n)=2T(n/2)+n log n is Theta(n log^2 n) by substitution after deriving the guess from a recursion tree.
8. A recursive tree search visits both children and performs constant local work. Explain why T(n)=2T(n/2)+Theta(1) is valid for a perfectly balanced tree but a node-count argument gives Theta(n) even when the tree is unbalanced.

Recursive Proofs

9. Give a total-correctness proof for hanoi: prove every emitted move is legal, the final arrangement is correct, and recursion terminates.
10. Prove binary_search_range preserves its candidate interval and strictly reduces hi-lo on every recursive call.
11. Prove the three-case decomposition used by maximum subarray is exhaustive, then prove the crossing scan finds the best crossing subarray.
12. Define valid input and representation contracts for factorial, ackermann, hanoi, and max_subarray_sum. Include empty ranges, arithmetic limits, output volume, and stack depth.

Stack Transformations

13. Convert recursive binary search and Euclid’s algorithm into loops. State the loop invariant that replaces each recursive induction hypothesis.
14. Convert recursive preorder traversal into an explicit-stack algorithm whose visit order exactly matches recursion. Determine the worst-case explicit-stack size for a chain and for a balanced tree.
15. Rewrite naive Fibonacci as memoized recursion, then bottom-up iteration. Compare call count, auxiliary storage, representable input range, and failure reporting.

Divide-and-Conquer Designs

16. Derive an algorithm that finds both minimum and maximum with at most 3n/2-2 comparisons for even n. Give its recurrence and exact count for powers of two.
17. Karatsuba multiplication uses three half-size recursive multiplications and linear additional digit work. Derive T(n)=3T(n/2)+Theta(n) and compare its exponent with the four-call schoolbook decomposition.
18. A majority element appears more than n/2 times. Design a divide-and-conquer candidate algorithm, identify the combine work, and compare its cost with the linear cancellation method.
19. Design a divide-and-conquer algorithm for the closest pair of points in the plane. Explain why checking only a constant number of neighbors in the midpoint strip is necessary for the Theta(n log n) target; a quadratic strip scan destroys the recurrence.