/****************************************************************************
 * fs2.c
 *
 * Computer Science 50
 * David J. Malan
 *
 * Computes n'th Fibonacci number as well as the number of times
 * every number in the sequence is computed.
 *
 * Demonstrates bad design (and instrumentation).
 ***************************************************************************/
       
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>


/* prototype */
long long fs(int);

/* instrumentation */
long long * counts;


int
main(int argc, char * argv[])
{
    int i, n;

    /* ensure proper usage */
    if (argc != 2)
    {
        printf("Usage: %s n\n", argv[0]);
        return 1;
    }

    /* validate n */
    n = atoi(argv[1]);
    if (n < 0)
    {
        printf("Input must be non-negative.\n");
        return 1;
    }

    /* allocate space for array of counts */
    counts = (long long *) malloc(n * sizeof(long long));
    if (counts == NULL)
    {
        printf("Out of memory!\n");
        return 2;
    }
    for (i = n; i >= 0; i--)
        counts[i] = 0;

    /* compute and print n'th number in Fibonacci sequence */
    printf("fs(%d) = %lld\n", n, fs(n));
    for (i = n; i >= 0; i--)
        printf("fs(%d) was called %lld time(s)\n", i, counts[i]);
}


/*
 * long long
 * fs(int n)
 *
 * Returns n'th number in Fibonacci sequence.
 */

long long
fs(int n)
{
    /* instrumentation */
    counts[n]++;

    /* compute n'th number */
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return (fs(n-1) + fs(n-2));
}