Characterizing Recurrence Relations

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

Divide and conquer recurrences:

• $T(n)=f(n)+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-$\mathrm{\Theta }$ number of activation records?
  • $\mathrm{\Theta }({\log }_{2}n)$
• Assume $a=2,b=2$, what is the big-$\mathrm{\Theta }$ number of activation records?
  • (Recall that ${\displaystyle \sum _{i=0}^n{2}^i=2^{n+1}-1}$)
  • $\mathrm{\Theta }(n)$

Linear recurrences:

• $T(n)=f(n)+a\times T(n-1)$
• Assume $a$ is 1, what is the big-$\mathrm{\Theta }$ number of activation records?
  • $\mathrm{\Theta }(n)$
• Assume $a>1$, what is the big-$\mathrm{\Theta }$ number of activation records?
  • $\mathrm{\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--;
        }
    }
}