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)$

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)=10$

• $T(n)=n+10+2T(n-1)$

Analyzing Recursive Algorithms: Stage 1

• Step one is to develop a recurrence.

• Typically:

  Initial Conditions

  $T(size\mathrm{\_}of\mathrm{\_}base\mathrm{\_}case)=\mathrm{\#}operations\mathrm{\_}required\mathrm{\_}for\mathrm{\_}base\mathrm{\_}case$

  Recurrence Relation

  $T(n)=\mathrm{\#}operations\mathrm{\_}in\mathrm{\_}call+\mathrm{\#}recursive\mathrm{\_}calls\times T(size\mathrm{\_}of\mathrm{\_}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)=0$

$T(n)=8+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…