$ $

Recurrences

• Reminder: “recurrence relations” 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:

• \(T(0) = 1\)

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

There is Nothing Special About Recursion:

    public static int maxOfArray(int[] arr) {
        int end = arr.length - 1;
        int mid = end / 2;

        int leftMax = maxRange(arr, 0, mid);
        int rightMax = maxRange(arr, mid+1, end);
        
        if (leftMax > rightMax) {
            return leftMax;
        } else {
            return rightMax;
        }
    }

• If maxRange does \(M(n)\) comparisons for an input of size \(n\), then maxOfArray does…

• \(T(n) = 2M(n/2) + 1\) comparisons.

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 split1(n - 1) + split1(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 == 1) {
        return 5;
    } else {
        int sum = 1;
        for (int i = 0; i < 7; i++) {
            sum *= 2;
        }
        return sum * fun(n - 1);
    }
}

\(T(??) = ??\)

\(T(n) = ??\)

Warm-up Exercise

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

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

\(T(n) = \color{red}{8} + \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 - (fun1(n - 1) + fun1(n - 1));
        }
    }

One More…

Write a recurrence relation that describes the number of assignments to sum performed by this method.

    public static int fun(int n) {

        if (n <= 1) {
            return 8;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fun(n - 1) + fun(n - 2);
        }
        return sum;
    }

One More…

Write a recurrence relation that describes the number of assignments to sum performed by this method.

    public static int fun(int n) {

        if (n <= 1) {
            return 8;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fun(n - 1) + fun(n - 2);
        }
        return sum;
    }

We need two initial conditions!

\(T(0) = 0\)

\(T(1) = 0\)

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

Part 2: Solving the Recurrence

Next time…