$ $

Characterizing Recurrence Relations

There are some common recurrence types that tend to come up when analyzing recursive algorithms.

Divide and conquer recurrences:

$T(n) = \color{red}{f(n)} + \color{green}{a \times T(n / b)}$
- Red part: cost per activation record
- Green part: number of activation records
- $b$ determines the recursion depth
- $a$ determines the recursion width
Assume $a = 1, b = 2$, what is the big-$\Theta$ number of activation records?
- $\Theta(\log_2 n)$
Assume $a = 2, b = 2$, what is the big-$\Theta$ number of activation records?
- (Recall that $\displaystyle \sum_{i=0}^n 2^i = 2^{n+1} - 1$)
- $\Theta(n)$

Linear recurrences:

$T(n) = \color{red}{f(n)} + \color{green}{a \times T(n-1)}$
Assume $a$ is 1, what is the big-$\Theta$ number of activation records?
- $\Theta(n)$
Assume $a > 1$, what is the big-$\Theta$ number of activation records?
- $\Theta(a^n)$
- Sometimes called a “chip and be conquered” recurrence.

Tail Recursion

A method is “tail recursive” if the recursive call is the last thing that happens.

public static int search(int[] numbers, int target, int index) {

    if (index < 0) {
        return -1;
    } else if (numbers[index] == target) {
        return index;
    } else {
        return search(numbers, target, index - 1);
    }
}

Tail Recursion

May be mechanically converted to a while loop.

public static int search1(int[] numbers, int target, int index) {

    while (true) {
        if (index < 0) {
            return -1;
        } else if (numbers[index] == target) {
            return index;
        } else {
            index--;
        }
    }
}

Is this tail recursion?

public static int sum(int[] numbers, int index) {

    if (index < 0) {
        return 0;
    } else {
        return numbers[index] + sum(numbers, index - 1);
    }

}

Sometimes possible to convert to tail recursive method

private static int sum1(int[] numbers, int index, int accumulator) {

    if (index < 0) {
        return accumulator;
    } else {
        accumulator += numbers[index];
        return sum1(numbers, index - 1, accumulator);
    }

}

Then we can remove recursion

private static int sum2(int[] numbers, int index, int accumulator) {

    while (true) {
        if (index < 0) {
            return accumulator;
        } else {
            accumulator += numbers[index];
            index--;
        }
    }
}