# Class 27: More Recursive Algorithms

Back to Analyzing Recursive Algorithms. On to Some Sorting Algorithms.

Held Tuesday, October 10, 2000

Summary

Today we continue our analysis of recursive algorithms.

Notes

• Are there questions on the current chapter of Bailey (the one on algorithm analysis)?
• You may want to start reading the chapter on sorting.
• Thursday's convocation: Will Talbert, Noyce Visiting Professor speaks on Studying the Origin of the Elements Using Radioactive Ion Beams. 11:00 in Harris.
• Why do they put Physicists in Harris?
• This past weekend, I went to a marriage celebration for folks I knew in college (at the University of Chicago, another liberal arts institution). Almost everyone I know went into "IT" (even though they were economics, history, philosophy, ... majors).

Overview

• Solving recurrence relations
• Exponentiation
• Algorithm design with divide and conquer
• Fibonacci

## A Quick Recap

• We've been analyzing the running time of recursive algorithms.
• Yesterday, we defined a function for the running time of our smallest algorithm with a pair of equations.
```f(1) = 2
f(n) = 5 + 2*f(n/2)
```
• Let's once again look at how we might determine the pattern of this function.
```f(1) = 2
f(2) = 5 + 2*f(1) = 5 + 2*2
f(4) = 5 + 2*f(2) = 5 + 2*(5 + 2*2) = 3*5 + 4*2
f(8) = 5 + 2*f(4) = 5 + 2*(3*5 + 4*2) = 7*5 + 8*2
```
• Do you see a pattern? I do
```f(n) = (n-1)*5 + n*2
```
• Is that the same pattern we worked out yesterday? It's similar.
```f(n) = 7*n - 5
```

## Generalizing the Technique

• The technique we've used is a good one for analyzing the running time of recursive functions, so let's generalize.
• Here's how I think of it:
• Start by defining a function, f, that represents the running time of your method.
• Determine the value of f for the base cases.
• Determine the value of f for the recursive cases. This will normally be a recursive function definition
• Build up from small parameters to large parameters.
• Eventually, you should see a pattern, so generalize.
• Note that it may also work to build down from large parameters to small parameters.
• How do you see the patterns? Mostly practice and luck.

## Running Times

Just to give you a sense of running times, here's a short table.

```N     O(1)    O(log2N)    O(N)    O(Nlog2N)    O(N2)    O(2N)

1   1        0          1          1          1         2

2   1        1          2          2          4         4

4   1        2          4          8         16        16

8   1        3          8         24         64       256

1000   1       10       1000     10,000  1,000,000      10300

8000   1       13       8000    100,000 64,000,000      a lot
```

## Exponentiation

• There are a number of techniques one can use for computing xn, where n is an integer.
• Complicated mathematics
• Multiply x*x*x*...*x n times
• Divide and conquer
• Although our algorithms will admit negative exponents, our analyses will assume positive exponents.
• As we observed, there are two techniques for doing the repeated multiplication: we can use iteration or recursion.
• Let's consider each function
```
/**
* An illustration of different mechanisms for computing x^n.
*
* @author Samuel A. Rebelsky
* @version 1.0 of October 1999
*/
public class Exponentiation {

// +---------+-------------------------------------------------
// | Methods |
// +---------+

/**
* Compute x^n by multiplying x*x*...*x n times.  Uses
* iteration as the mechanism for repetition.
*/
public static double expA(double x, int n) {
// Handle negative exponents.  x^(-n) = 1/(x^n)
if (n < 0) {
return 1/expA(x,-n);
}
// Prepare to compute the product.
double product = 1;
// Multiply by each x.  (Note that 1*x*x*...*x = x*x*...*x.)
for (int i = 0; i < n; ++i) {
product = product * x;
} // for
// That's it, we're done.
return product;
} // expA(double,int)

/**
* Compute x^n by multiplying x*x*...*x n times.  Uses
* recursion as the mechanism for repetition.
*/
public static double expB(double x, int n) {
// Handle negative exponents.  x^(-n) = 1/(x^n)
if (n < 0) {
return 1/expB(x,-n);
} // if (n < 0)
// Base case: x^0 is 1.
if (n == 0) {
return 1;
} // if (n == 0)
// Recursive case: x*x*...*x = x*(x*...*x)
// That is: x^n = x*(x^(n-1))
else {
return x * expB(x, n-1);
} // Recursive case, if (n > 0)
} // expB(double,int)

/**
* Compute x^n by a recursive divide-and-conquer algorithm.
*/
public static double expC(double x, int n) {
// Handle negative exponents.  x^(-n) = 1/(x^n)
if (n < 0) {
return 1/expB(x,-n);
} // if (n < 0)

// Base case: x^0 is 1.
if (n == 0) {
return 1;
} // Base case: n == 0

// Recursive case (when n is odd)
//   x*x*...*x = x*(x*...*x)
//   That is: x^n = x*(x^(n-1))
else if (n % 2 == 1) {
return x * expC(x,n-1);
} // Recursive case (when n is odd)

// Recursive case (when n is even)
//   Let n be 2k
//   x^n = x^(2k) = x^k * x^k
else {
int k = n/2;
double tmp = expC(x,k);
return tmp*tmp;
} // Recursive case (when n is even)
} // expC
} // class Exponentiation

```

### Repeated Multiplication with Iteration

• The first version, `expA`, is perhaps the easiest to analyze.
• There is some preparatory work. That takes a constant number of steps. We'll call that a1.
• There is a loop that is repeated n times.
• Each time through the loop, a constant number of steps are done. We'll call that a2.
• After the loop, a few more steps are done (okay, just a return). We'll call that a3.
• What's the approximate running time?
• a1 + a2*n + a3
• Using Big-O notation, we can throw away the constants and get O(n).

### Repeated Multiplication with Recursion

• The second version, `expB`, is somewhat more difficult to analyze because of the recursion.
• Here are the basic steps
• exp(x,0) is 1
• exp(x,n) is x * exp(x, n-1)
• But how do we analyze the running time of this algorithm?
• One technique that is typically fruitful (although somewhat mathematical), is to define a function, fb(n), that represents the the number of steps the algorithm takes on input of size n.
• We know that when n is 0, the function takes a constant number of steps.
• fb(0) = b1
• When n is greater than 0, the function takes some constant number of steps before and after the recursive call plus the time for the recursive call.
• We'll call the constant extra steps b2
• How do we determine the number of steps for the recursive call (`expB(x,n-1)`)? Hmmm ... Wait! fb is supposed to tell us that!
• fb(n) = b2 + fb(n-1)
• We've defined the running time recursively, too. That doesn't help us much if we want to do some Big-O analysis. So let's figure out what fb really is.
• Let's start by repeatedly applying our recursive rule ...
• fb(n) i+ = b2 + fb(n-1)
• = b2 + b2 + fb(n-2)
• = b2 + b2 + b2 + fb(n-3)
• We might then generalize
• fb(n) = k*b2 + fb(n-k)
• Can we ever get rid of the recursive term? Yes! When n = k, n-k is 0, and we know the value of fb(0).
• fb(n) = n*b2 + b1
• As you might be able to tell, that's just O(n).

## Detour: Algorithm Design: Divide and Conquer

• As you may have noted, binary search is much faster than sequential search.
• How did we make binary search run faster? We took a particular approach to the data:
• We broke the input into half
• We recursed on one half.
• The idea of breaking the input in half will be useful in developing algorithms to solve a variety of problems. It is a key part of your ``programmer's toolbox''. Make sure to consider whether it is appropriate each time you visit a problem.

## Exponentiation with Divide and Conquer

• Can we use divide-and conquer to solve the exponentiation problem (or to improve our solution)?
• What can we divide in half? (What gives the ``size'' of the problem?)
• Here's another version of exponentiation, based on a divide-and-conquer strategy.
```  /**
* Compute x^n by a recursive divide-and-conquer algorithm.
*/
public static double expC(double x, int n) {
// Handle negative exponents.  x^(-n) = 1/(x^n)
if (n < 0) {
return 1/expB(x,-n);
} // if (n < 0)

// Base case: x^0 is 1.
if (n == 0) {
return 1;
} // Base case: n == 0

// Recursive case (when n is odd)
//   x*x*...*x = x*(x*...*x)
//   That is: x^n = x*(x^(n-1))
else if (n % 2 == 1) {
return x * expC(x,n-1);
} // Recursive case (when n is odd)

// Recursive case (when n is even)
//   Let n be 2k
//   x^n = x^(2k) = x^k * x^k
else {
int k = n/2;
double tmp = expC(x,k);
return tmp*tmp;
} // Recursive case (when n is even)
} // expC
```
• We'll use the same technique of ``define a function whose value is the number of steps the algorithm takes''. This time, we'll call the function fc.
• This time, life is a little harder because we have two different recursive cases. (Odd and Even).
• Fortunately, the odd case transforms into the even case. That is, if n is odd, then on the next recursive call it will be even.
• In effect, by choosing a bigger value for the ``constant'' work, we can pretend that n is divided by two in each recursive call.
• If it makes it easier, think about replacing the lines that read
```    else if (n % 2 == 1) {
return x * expC(x,n-1);
} // Recursive case (when n is odd)
```
with
```    else if (n % 2 == 1) {
double tmp = expC(x, (n-1)/2);
return x * tmp * tmp;
} // Recursive case (when n is odd)
```
• So
• fc(0) = c1
• fc(1) = c2
• fc(n) = c3 + fc(n/2)
• What function is this? Again, we will try some analysis by hand to figure it out.
• A few applications of the recursive rule
• fc(n)
• = c3 + fc(n/2)
• = c3 + c3 + fc(n/4)
• = c3 + c3 + c3 + fc(n/8)
• Can we generalize? Certainly.
• fc(n) = k*c3 + fc(n/2k)
• When can we get rid of the recursive term? When n/2k is 1.
• That is, k is ``the power to which you must raise 2 in order to get n''.
• Fortunately, there's a name for that value. We call it log2(n).
• Hence,
• fc(n) = log2(n)*c3 + c2
• That is, this algorithm is an O(log2(n)) algorithm.

## Fibonacci

• We can compute Fibonacci numbers
• iteratively, starting at the bottom and working our way up
• recursively, using the rule that fib(n) = fib(n-1) + fib(n-2)
• The iterative Fibonacci calculation is fairly easy to analyze. Since we step through n different Fibonacci numbers and do a constant amount of calculation for each, that algorithm is O(n).
• The recursive version is much harder. Again, we'll use a function to represent the number of steps the algorithm takes on input of size n. We'll just call this function f.
• Two base cases:
• f(0) = d1
• f(1) = d2
• One recursive case
• f(n) = d3 + f(n-1) + f(n-2)
• Hmmm ... this is surprisingly similar to the function that defines Fibonacci.
• Thus, the number of steps to compute the nth Fibonacci number is more than the value of the nth Fibonacci number.
• This function grows fairly quickly, but how quickly?
• We'll ignore the d3 to make our life easier. (No, you can't always do so, but it seems safe in this case.)
• We'll take advantage of the observation that f(n-2) <= f(n-1)
• While the observation is fairly obvious, the decision to use it is not. You should not expect to have come up with it on your own.
• So, let's try applying that observation
• f(n) = f(n-1) + f(n-2)
• f(n) <= f(n-1) + f(n-1)
• f(n) <= 2*f(n-1)
• Okay, now we can try applying that rule a few times.
• f(n) <= 2*f(n-1)
• f(n) <= 2*2*f(n-2)
• f(n) <= 2*2*2*f(n-3)
• Can we generalize? Sure
• f(n) <= 2k*f(n-k)
• Does this lead to a natural answer. Let k = n.
• f(n) <= 2n*d1
• f(n) is in O(2n)
• This may be painfully slow (as you've seen)
• But this is an upper bound, and it may be much too large. Let's try a lower bound.
• Again, we'll use the relationship between f(n-1) and f(n-2), but in the opposite direction.
• f(n) = f(n-1) + f(n-2)
• f(n) >= f(n-2) + f(n-2)
• f(n) >= 2*f(n-2)
• We can now apply that rule a few times
• f(n) >= 2*f(n-2)
• f(n) >= 2*2*f(n-4)
• f(n) >= 2*2*2*f(n-6)
• Generalizing,
• f(n) >= 2k*f(n-2k)
• When k = n/2, we're done
• f(n) >= 2(n/2)*d1
• This is a lower bound, rather than an upper bound. Hence, we cannot use Big-O. Instead, we use little-o for lower bound.
• f(n) is in o(2(n/2)).
• This is still painfully slow.

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Tuesday, 10 October 2000

• Filled in the details.

Back to Analyzing Recursive Algorithms. On to Some Sorting Algorithms.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.