============================================================================
           Faculty of Applied Science and Engineering, University of Toronto
                     CSC181: Introduction to Computer Programming, Fall 2000

Practical Notes, Week 8: Recursion
============================================================================

The purpose of this practical is to have you work with recursion.

You will not be graded for this practical.

----------
Your Tasks
----------

1. Write a program which prints all of the rows up to the nth row of
   Pascal's triangle, using no loops, only recursion.

   Recall that Pascal's triangle, up to row 5, looks like this:

   row 0:  1
   row 1:  1   1
   row 2:  1   2   1
   row 3:  1   3   3   1
   row 4:  1   4   6   4   1
   row 5:  1   5   10  10  5   1

   The numbers on the ends of the rows are all 1. Each other number is
   the sum of the number directly above it and the number above and to
   the left.

2. Suppose a is an array of n ints, each representing the weight of a
   coin. For this particular question, assume that exactly one of the
   coins is fake and weighs less than the others. All the real coins
   weigh the same amount.

   Assume that you have a function with the following prototype, that
   correctly represents the action of a balance scale:

   int weigh(int a[], int i, int j, int p, int q);

   If 0 <= i <= j < p <= q <= n-1, then weigh(a, i, j, p, q) compares
   the sum weights of a[i..j] and a[p..q] and returns:

     == 0 if the weights are equal
     > 0 if the weight of a[i..j] is > the weight of a[p..q]
     < 0 if the weight of a[i..j] is < the weight of a[p..q]

   Write a recursive function that finds (i.e. returns the index of)
   the fake coin in a, using lg n (or close to lg n) calls to weigh,
   where 'lg n' is "log base 2 of n". (Can you do better than lg n?)

   To see whether your function actually works, you should also
   implement the weigh function.