// This program uses code from "Algorithms in C, Third Edition,"
//               by Robert Sedgewick, Addison-Wesley, 1998.

#include <stdio.h>
#include <stdlib.h>


int Fibonacci(int number)
{
   // Creating memory for the array of solutions.
   int * solutions = malloc(sizeof(int) * (number +1));
   int index;
   
   // Marking the solutions to all cases as "unknown".
   // We use the convention that -1 stands for "unknown".
   for (index = 0; index <= number; index++)
   {
      solutions[index] = -1;
   }
   
   int result = Fibonacci_helper(number, solutions);
   free(solutions);
   return result;
}

int Fibonacci_helper(int number, int * solutions)
{
   // if problem already solved, return stored solution.
   if (solutions[number] != -1)
   {
      return solutions[number];
   }
   
   int result;
   
   // base cases.
   if (number == 0) result = 0;
   else if (number == 1) result = 1;
   
   // recursive case
   else 
   {
      int result1 = Fibonacci_helper(number-1, solutions);
      int result2 = Fibonacci_helper(number-2, solutions);
      result = result1 + result2;
   }
  
   solutions[number] = result;
   return result;
}


int main()
{
   int N;
   while(1)
   {
      printf("Enter an integer N: ");
      scanf("%d", &N);
      if (N < 0) break;
      int f = Fibonacci(N);
      printf("    Fibonacci(N) = %d\n", f);
   }
   return 0; 
}