$ $

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--;
        }
    }
}