$ $

Recurrences

• Reminder: "recurrences" are recursive functions.

• E.g.:

  \(f(n) = f(n-1) + 1\)

• Finding closed-form solutions requires that we provide initial conditions:

  \(f(0) = 1\)

Counting Activation Records

• Draw a recursion trace for split(3):

  public static int split(int n) {
      if (n == 0) {
          return 1;
      } else {
          return split(n - 1) + split(n - 1);
      }
  }

• Express the number of activation records as a recurrence relation:

• \(T(0) = 1\)

• \(T(n) = 1 + 2T(n - 1)\)

Counting Operations

• More typically, we want to count the number of steps executed by a recursive algorithm:

          public static int split1(int n) {
  
              for (int i = 0; i < n + 10; i++) {
                  //BASIC OPERATION HERE.
              }
  
              if (n == 0) {
                  return 1;
              } else {
                  return split(n - 1) + split(n - 1);
              }
          }
  

• \(T(0) = \color{red}{10}\)

• \(T(n) = \color{red}{n + 10} + \color{green}{2T(n-1)}\)

Analyzing Recursive Algorithms: Stage 1

• Step one is to develop a recurrence.

• Typically:

  Initial Conditions

  \(T(size\_of\_base\_case) = \#operations\_required\_for\_base\_case\)

  Recurrence Relation

  \(T(n) = \#operations\_in\_call + \#recursive\_calls \times T(size\_of\_calls)\)

Warm-up Exercise

Develop a recurrence that describes the number of multiplication operations performed by the following code block:

public static int fun(int n) {
        if (n == 0) {
            return 5;
        } else {
            int sum = 1;
            for (int i = 0; i < 4; i++) {
                sum *= 2;
            }
            return sum * fun(n - 1);
        }
    }
}

\(T(0) = ??\)

\(T(n) = ??\)

Warm-up Exercise

public static int fun(int n) {
        if (n == 0) {
            return 5;
        } else {
            int sum = 1;
            for (int i = 0; i < 4; i++) {
                sum *= 2; // Four here.
            }
            return sum * fun(n - 1); // One here.
        }
    }
}

\(T(0) = \color{orange}{0}\)

\(T(n) = \color{red}{5} + \color{green}{T(n-1)}\)

Another Exercise

Write a recurrence relation that describes the number of additions performed by this method.

   public static int fun1(int n) {
        if (n == 0) {
            return 20;
        } else {
            
            int result = 2 * n;

            return result - (fun(n - 1) + fun(n - 1));
        }
    }

Part 2: Solving the Recurrence

Next time...