Recursion and Divide & Conquer

5.1Functions

Functions improve reusability, modularity, readability, and maintainability.

def function(arguments):
    steps
    return result

5.2Recursive Functions

Each recursive call works on a smaller instance of the same problem. Correct recursion requires both a stopping condition and progress toward that condition.

def recursive_function(parameters):
    if base_case_condition:
        return result
    else:
        return recursive_function(smaller_problem)

5.3Recursive Factorial

Factorial is defined for nonnegative integers. The base value is 0! = 1; for n ≥ 1, n! = n × (n − 1) × ··· × 1. Therefore its recursive definition is n! = n × (n − 1)!.

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

Once the base case returns 1, the calls unwind: 2 × 1, 3 × 2, 4 × 6, and finally 5 × 24 = 120.

Running time

Each call performs constant work and reduces n by one. The recurrence is:

There are n calls, so the running time is Θ(n).

5.4Recurrence Relations

The four methods introduced in the lecture are:

1. Substitution: repeatedly expand the recurrence until a pattern appears.
2. Recursion tree: show the work at every level and add the level costs.
3. Master Theorem: compare the recursive work with the non-recursive work.
4. Akra–Bazzi: handle more general divide-and-conquer recurrences.

5.5Substitution Method

Start with the factorial recurrence and expand it one step at a time:

T(n) = T(n - 1) + c
     = T(n - 2) + 2c
     = T(n - 3) + 3c
     ...
     = T(n - k) + kc

The expansion reaches the base case when n − k = 1, so k = n − 1. Therefore:

Exercises

5.6Recursion-Tree Method

A recursion tree turns a recurrence into levels. Each node represents one subproblem; the value written at the node is the work done outside its recursive calls.

T(n) = 2T(n/2) + cn
     = 2[2T(n/4) + c(n/2)] + cn
     = 4T(n/4) + 2cn
     = 8T(n/8) + 3cn
     ⋮
     = 2^k T(n/2^k) + kcn

Every level costs cn, and the tree has log₂ n + 1 levels. Hence the total is Θ(n log n).

Three-way recurrence tree

T(n) = 3T(n/4) + cn²
     = 3[3T(n/16) + c(n/4)²] + cn²
     = 9T(n/16) + cn²(1 + 3/16)
     = 27T(n/64) + cn²(1 + 3/16 + (3/16)²)
     ⋮
     = 3^k T(n/4^k) + cn² Σ(i=0 to k−1)(3/16)^i

Uneven split recurrence tree

Tree patterns and results

5.7Master Theorem

The Master Theorem applies to recurrences of the form:

• a is the number of recursive subproblems.
• n/b is the size of each subproblem.
• f(n) is the divide/combine work.
• nlogba represents the recursive tree’s leaf growth.

Compare f(n) with nlogba:

5.8Master-Theorem Examples

5.9Decreasing Recurrences

Some recursive algorithms reduce the input by a fixed amount rather than dividing it:

For tight bounds, assume f(n) = Θ(nk), k ≥ 0, and a positive constant base-case cost. The lecture’s Big-O forms remain valid upper bounds.

When 0 < a < 1, this is an algebraic recurrence coefficient—not a literal fractional number of recursive calls.

5.10Dividing Recurrences

The lecture’s generalized form is:

First compute logba and compare it with k.

For example, T(n)=2T(n/2)+Θ(n) has log₂2 = 1 = k and p=0, so Θ(n log n).

The earlier recurrence T(n)=4T(n/2)+n²/log n has log₂4=k=2 and p=−1. The generalized theorem therefore gives Θ(n² log log n).

5.11Binary Search

Binary search finds a target in a sorted array. Each unsuccessful comparison discards half of the remaining search interval. Its best-case time is Θ(1); its average- and worst-case time is Θ(log n).

Iterative version

def binary_search(array, key):
    low, high = 0, len(array) - 1

    while low <= high:
        mid = low + (high - low) // 2
        if array[mid] == key:
            return mid
        if array[mid] < key:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Recursive version

def binary_search_recursive(arr, low, high, target):
    if low > high:
        return -1

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    if target < arr[mid]:
        return binary_search_recursive(arr, low, mid - 1, target)
    return binary_search_recursive(arr, mid + 1, high, target)

5.12Recursion Practice

Write a base case and a recursive case for each problem:

1. Generate the Fibonacci sequence.
2. Find the sum of the first n natural numbers.
3. Reverse a string.
4. Check whether a string is a palindrome.
5. Count the digits in a number.
6. Print every element of an array.

def sum_n(n):
    if n <= 0:
        return 0
    return n + sum_n(n - 1)

5.13What Is Divide and Conquer?

Binary search as divide and conquer

• Divide: split the sorted array around its middle element.
• Conquer: search only the half that can contain the target.
• Combine: no merge is needed; return the result directly.

5.14Characteristics of Divide and Conquer

Standard examples include binary search, merge sort, quicksort, and Strassen’s matrix-multiplication algorithm.

5.15General Algorithmic Template

def divide_and_conquer(problem):
    if base_case(problem):
        return base_solution(problem)

    subproblems = divide(problem)
    subresults = [
        divide_and_conquer(sub)
        for sub in subproblems
    ]
    return combine(subresults)

The recurrence is determined by three design choices: how many subproblems are created, how large they are, and how much work the divide/combine steps require.

5.16Strengths and Limitations

Limitations

• Recursive calls consume stack space and add call overhead.
• The combine step can be expensive or difficult to design.
• Unbalanced splits may destroy the expected performance.
• Problems with heavily overlapping subproblems are often better handled by dynamic programming.