Assignment 5
0) Consider the following program and figure out what it does.
You may wish the run it with some non-negative int data.
Please do not tell others in your class what it does.

#include <stdio.h>
int main(){ int a, b;
  while (scanf("%d %d", &a, &b) == 2 )
    printf("%d %d %d", a, b, mystery( a, b ) );
}
int mystery ( int a, int b ) { return help( a, b, 1); }
int help ( int a, int b , int c) {
  return b==0 ? c : help( a*a, b/2, b%2==0 ? c: c*a); 
}
Are the calls to the help method tail calls? Discuss briefly.

What are the pre- and post-conditions of the mystery and help functions?
(There is some flexibilty in the pre-conditions. A tighter pre-
may simplify the post- but do not simplify it so the method is useless.)

Rewrite the main method to compute the same result using one for loop
and no auxiliary functions.  What is the loop invariant for your for loop?

1) Write a similar program to compute choose(n,m) where 0 <= m <= n.
These are the entries in Pascal's triangle and the binomial coefficients.
Write it using tail calls where possible and use a help function.
There should be no explicit loops in the choose and help functions.
Give the pre- and post-conditions for the help function.
I think the post-condition for choose(n,m) is
  RET = n! / ( m! * (n-m)! )
Of course your program should not use division or the factorial function.
Use + to compute elements of Pascal's triangle.

Then write it using nested for loops and give the loop invariants
as comments.

The formula   choose(n,m)=choose(n-1,m-1) + choose(n-1, m)
is hopelessly expensive on its own. The idea is to compute the rows
of Pascal's triangle one at a time (overwriting an array). This can be
made tail recursive if extra parameters are used to carry the answer so
far.