Recursion Exercises

1. What are the two questions for constructing recursive solutions?

2. Binary Search is a classical optimal search algorithm:
   Look at the middle element of an array.
   If the number you're searching is larger than the middle element, search the upper half.
   If the number you're searching is smaller than the middle element, search the lower half.
   Otherwise, the number is found.

   1. Apply the two questions for constructing a recursive solution to Binary Search:
   2. Outline the an algorithm for a recursive Sequential Search and a recursive Binary Search
   3. Write the code for recursive Sequential Search and recursive Binary Search
   4. Discuss with your neighbor(s) the Big-Ohs of Sequential Search and Binary Search:
      To calculate the worst-case Big-Oh for Binary Search for an array of size n consider the following:
      After 1 iteration, there are n/2 elements left to search.
      After 2 iterations, there are n/2/2 (or n/2²) elements left to search.
      After 3 iterations, there are n/2/2/2 (or n/2³) elements left to search.
      After 4 iterations, there are n/2/2/2/2 (or n/2⁴) elements left to search.
      After k iterations, there are n/2^k elements left to search.
      In the worst case, searching stops when there is 1 element left to search, so n/2^k = 1
      Rearranging the equation: 2^k = n
      Taking the log of both sides: log₂ 2^k = log₂ n
      Simplifying: k log₂ 2 = log₂ n
      Simplifying: k = log₂ n
      
3. Identify answers for the two questions for constructing a recursive solution, write an outline and then a recursive solution to calculate a Fibonacci number:
   F₁ = 1
   F₂ = 1
   F_n = F_{n - 1} + F_{n - 2}
4. Identify answers for the two questions for constructing a recursive solution for the Tower of Hanoi problem. (Assume that you can make calls like moveDisc( tower1, tower2 ) to move a disc from a specified tower to another specified tower.) Also, write an outline and a recursive solution.
5. Working together with those at your table, apply the two questions for constructing a recursive solution for making change for a given amount of money. Let's assume that we are only dealing with standard US coins (with values 1, 5, 10, 25). For example, there are 242 different ways to combine pennies, nickels, dimes and quarters to make $1.00. There are 6 ways to combines those coins to make $0.15 and 4 ways for $0.10. Make sure that you can solve simple problems (like $0.05, $0.06, $0.10 and $0.15) by hand before thinking about your recursive solution.

Last Modified: