CS 14 - Fibonacci Table

Once upon a time, a learned gentleman and mathematician in the city of Pisa asked the following question:

A certain man put a pair of rabbits in a place surrounded on all
sides by a wall. How many pairs of rabbits can be produced from that
pair in a year if it is supposed that every month each pair begets a
new pair which from the second month on becomes productive?

By itself this is no great event, however the gentleman in question was named Leonardo Pisano, (aka Fibonacci), he was writing one of the few mathematical texts to be developed in Europe in the 13th century, and he solved the question quite nicely by examining the following facts:

The first month there is one pair of rabbits
The second month there is one pair breeding, and one pair just born
The third month there are two breeding pairs, and one pair just born
The fourth month there are three breeding pairs, and two pairs just born
The fifth month there are five breeding pairs, and three pairs just born
On the nth month, there are as many just born as there were breeding the previous month, and those will all be breeding next month.

Application of this rule generates the sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
For every element n after n=2, this is simply the sum of element n-1 and n-2. This sequence is called the Fibonacci Sequence, and can be found throughout math and science.

Tables

In Computer Science we use the Fibonacci Sequence a lot as a teaching tool for recursion. However, in this assignment, we are not going to use simple recursion, instead we are going to demonstrate a very simple case of a more powerful technique: dynamic programming. Dynamic programming is like recursion in that you break a problem down into easier problems, but instead of simply calling a function to calculate the result of a previous problem, we first check if we have ever calculated that result before by looking in a table of old results.

A table for the Fibonacci Sequence is simply an array. To begin with, the first two elements of the array are filled in with value 1. To find any other value n, we simply check the table at that location: if it is not filled in, we perform the recursion as normal. If it is, we return that value.

Specs

Write a program that allows the user to enter a value n (in the range [1-45]) and have the nth digit of the Fibonacci sequence (counting from 1) printed out. When the user enters a value of -1, terminate the program. When the user enters anything outside of the range [1-45], do not print anything.

To begin with, your program should print this message:

Fibonacci Sequence Calculator
Enter a -1 to quit, or an int n in the range [1-45] to
see the nth value of the Fibonacci sequence

To earn full credit on this, you should implement a table storing the values of the Fibonacci sequence, but do NOT just fill in all the values of the table from 1-45, your table may only be as large as the largest index requested so far (that is, if the largest index the user has entered is 10, then the table should be no larger than 10 ints). To do this, you will need to use:

Global variables / function-static variables - We would prefer static
Dynamic array allocation
(Possibly) recursion

Hints

Remember to initialize the table!
What value will "empty" cells in your table have?
Will a call to calculate Fib(n) ever require Fib(m) for m < n?
You might want to try making the program work with a statically allocated table of size 45 to get the calculations working before working with the memory allocation.
Write a function int* expand(int* old, int oldSize, int newSize) that takes an array and its size and:
- Allocates a new array of size newSize
- Copies the elements of old into the new array
- Frees up the memory for the old array
- Returns the new array
(Remember that pointers and arrays are equivalent).
Use expand to grow your table when needed.