Outline

• random numbers
• recursion
• examples of recursion
• implementation of recursion using a stack
• principles of recursion
• binary search
• more examples of recursion

Random numbers

• tossing a fair coin is truly random -- there is no way to predict what the next toss will give
• computers do not find it easy to toss coins
• instead, beginning with a specific number (the seed), they apply a complicated function to yield a new number
• this new number is a pseudo-random value: it is computed, and therefore not random, but there is no easy way to predict the new number from the old (without knowing the exact function), and so it looks like a sequence of random numbers
• the initial seed can be a fixed value (e.g. 1), to give a repeatable sequence of random numbers (good for debugging code)
• or, the initial seed can be selected almost at random, e.g. the time of day when the program is run, to give a different sequence each time
• Java's Math.random() returns a double with a value uniformly distributed between 0 and 1
• Java Random by default is initialized to the current day and time, but the programmer can explicitly specify the seed

Recursion in nature

• to recur means to happen again and again
• there are many examples of recursion in nature
• for example, a tree's trunk divides into branches
• each branch divides into smaller branches
• this continues until the branches become twigs that carry leaves
• in this case, the recursion consists of successive splitting into smaller, similar structures
• the recursion ends at the leaves

Example of Recursion: computing factorials

• n! (n factorial) can be defined as n * (n - 1)! -- for n > 0
• this is a recursive definition
• to end the recursion, we define 1! = 0! = 1
• there are many examples of recursion in mathematics
• to implement this factorial function, we could define methods such as:

       public int factorial(int n) {
          if (n <= 1) {
              return 1;
          } 
          return n * factorialOfNMinusOne(n - 1);
       }
  
       public int factorialOfNMinusOne(int nMinusOne) {
          if (nMinusOne <= 1) {
              return 1;
          } 
          return nMinusOne * factorialOfNMinusTwo(nMinusOne - 1);
       }
  
       public int factorialOfNMinusTwo(int nMinusTwo) {
          if (nMinusTwo <= 1) {
              return 1;
          } 
          return nMinusTwo * factorialOfNMinusThree(nMinusTwo - 1);
       }
  

  and so on
• most programming languages, including Java, allow us to collapse these different (potentially unlimited) method declarations into a single piece of code:

       public int factorial(int n) {
          if (n <= 1) {
              return 1;
          } 
          return n * factorial(n - 1);
       }
  

  each subsequent call to factorial has its own copy of the variable n, distinct from all the others

Example of Recursion: computing the greatest common divisor

• the greatest common divisor of two number n and m (m > n) can be defined recursively:
  1. gcd(m, n) = n if n is a divisor (factor) of m, that is, m % n = 0
  2. otherwise, gcd(m, n) = gcd(n, m % n)
• this naturally gives rise to a recursive implementation:

       public int gcd(int m, int n) {
          if (m % n == 0) {
              return n;
          } 
          return gcd(n, m % n);
       }
  

Implementation of Recursion

• how can each invocation of the same method have a different copy of the parameter?
• several things must be remembered for each invocation:
  • the values of the parameters
  • the values of local and loop variables
  • the return address: the place where execution must resume once the method invocation is complete
• whenever a method is called, Java pushes all this information onto a system stack, which is not visible to the Java programmer
• whenever a method returns (or throws an exception), Java pops all this information from the stack, and starts executing code again from the return address
• this works because execution of a method is entirely contained within the enclosing method, so the LIFO discipline is appropriate

Recursion instead of loops

• some programming languages don't even have loops, and use recursion instead
• any loop can be written as a recursive method:

  for (int i = 0; i < 5; i++) {
    count = count + 1;
  }
  

  can be rewritten as:

  public int countToFive(int i) {
     if (i < 5) {
        return 1 + countToFive(i + 1);
     } else {
        return count;
     }
  }
  ...
     count = countToFive(0);
  

Recursion structure

• infinite loops are not usually useful
• similarly, infinite recursion is not usually useful (and will result in stack overflow)
• so, every recursive method needs one or more base cases, for which it can compute the answer without using recursion
• every recursive method also needs one or more recursive cases

Breaking up a problem

• many problems have:
  • an obvious solution when they are small, and
  • a way to make a big problem into a smaller problem
• if this is the case, we can solve any size problem!
• for example, I know how to walk down one block
• assuming I can get to within one block of my destination, I know I can get to my destination
• so the smaller problem is, how do I get to within one block of my destination?
• recursion: first I must get to within one block of (one block from my destination)
• to get there, I must first get to within one block of (one block from (one block from my destination))
• etc.
• if I can always get one block closer to my destination, I am guaranteed to be able to get to my destination

recursive thinking: Binary Search

• can I break up a problem into one or more similar and smaller problems?
• example: find a number in a phone book
• one solution: search through all the numbers with while or for loops: this is an iterative solution
• a better solution: use recursion (recursive solution)
• if I am at the right entry, I know how to look it up
• the phone book is alphabetized
• if I have many entries, I can look at the middle one, and determine whether the entry I want is:
  • where I am looking: problem solved (a base case), or
  • before where I am looking: problem is smaller, or
  • after where I am looking: problem is smaller
• so, either I've solved the problem, or I can call the same method recursively to solve the smaller sub-problem
• for this problem, I actually have to keep track of the start and the end of the part of the phone book that might still have the desired name
• each time I look in the phone book, this part gets smaller
• at some point, this part gets so small that if I don't find the desired name, I know it is not in the phone book: this is the other base case for this recursive solution
• this is called binary search, because at each step I break the problem into two equal parts
• In-class exercise: what is the runtime of binary search?

Binary Search Implementation

/* @returns: the index of the item being searched, or -1 */
/* the element is between data[first] and data[last], inclusive */
public int binarySearch(int value, int [] data, int first, int last) {
  if (first > last) {          // base case: empty array
    return -1;
  }
  // if last >= first, last >= middle >= first
  int middle = (last + first) / 2;  // middle ~= first + (last - first) / 2
  if (data[middle] == value) {    // base case: found
    return middle;
  }
  if (data[middle] < value) {  // first recursive case: value in upper half
    return binarySearch(value, data, middle + 1, last);
  } else {  // second recursive case: value must be in the lower half
    return binarySearch(value, data, first, middle - 1);
  }
}

• reminder: binary search only works if the underlying array is in order
• how can I guarantee that this binary search code terminates?

Proving that a recursive method terminates

• prove that every recursive case gets closer to a base case
• for example, in binary search:
  • the base case is when the value is found, or first > last
  • on each recursive call, either first moves towards last, or last moves towards first, by at least one: because middle is not less than first, middle + 1 is bigger than first, and because middle is not greater than last, middle - 1 is less than last
• in general, must prove that the recursive case approaches the base case
• for factorial, a correct proof would depend on whether the base case is (n <= 1) or (n == 0) -- if the latter, the recursion does not terminate for n < 0

Details: comparing objects

• most objects have an absolute ordering
• for example, Strings or Integers
• we can rewrite the above code to compare an array of Object values
• to a target value defined to implement the Comparable interface:

  int compareTo(T value);
  

• x.compareTo(y) returns:
  • a value less than zero if x < y
  • a value of zero if x == y
  • a value greater than zero if x > y
• this can be used instead of the integer comparisons in the binary search method

how does this work?

• suppose I call printInt(8)
• no recursion is needed -- the first condition is true
• suppose I call printInt(82)
• the first condition is false, so the else clause executes
• printInt(8) is called, just as before
• what is the value of toPrint?
  • each invocation of printInt has its own value of toPrint
  • so the first invocation has toPrint = 82
  • the second invocation has toPrint = 8
  • although the two parameters called "toPrint" have the same name, they are parameters to different calls of printInt
  
• similarly, we can trace this Recursive program

In-class exercise

• write a recursive method
• to print integers
• printing a comma every 3 digits
• for example, 1,234,567,890

computing fibonacci numbers

• the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, ...
• the n-th fibonacci number fib(n) is simply defined as fib(n-1) + fib(n-2)
• this is clearly a recursive definition
• fib(1) == fib(2) == 1

     static int fib(int n) {
       if (n <= 2) {
         return 1;
       }
       return fib(n - 1) + fib(n - 2);
     }
  

• the only problem is this is very inefficient: computing fib(100) must compute fib(99) and fib(98).
• but computing fib(99) also recomputes fib(98), as well as fib(97)
• there are ways around this -- instead of computing from the large numbers, compute the small values first