CS 246 Lab 9

Write a recursive function long fib(int n) that computes the $n$th Fibonacci number. They are defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1}+F_{n-2}.$ Write a program called fib1 that prints the first n Fibonacci numbers, where n is a command line argument. Make sure you check to see whether an argument is supplied by the user. How large can n be before the program slows down too much?
Rewrite the program in the following way. In the fib function, declare a static array of size 100, with the first element initialized to -1.
```
static long a[100] = { -1 };
```
Then check to see whether the first element of the array is -1. If so, then fill the array with Fibonacci numbers. After it is filled, return a[n]. Declaring a variable static makes it retain its values between calls to the function. Call the new program fib2.
1. Write a function long factorial(int n) that computes $n! = n(n-1)(n-2)\ldots (2)(1)$. $0!$ is defined to be 1. Use a for loop.
2. Write a function long binomial(int n, int k) that computes a binomial coefficient. binomial(n, k) is defined to be $${n \choose k} = \frac {n!} {k!(n-k)!}.$$ It counts the number of ways to choose of committee of $k$ people from a group of $n$ people.
3. Write a program called pascal that takes a single command line argument $n$ and prints a Pascal's triangle of size $n$. The $k$th entry in the $n$th row is $n \choose k$.
  For example, the Pascal's triangle of size 5 is:
```
                          1
	              1        1
                 1        2        1
             1        3        3        1
	 1        4        6        4        1
```
  Use the spacing shown above.