Fibonacci function uses cache

cached_fibonacci.c

#include <stdio.h>

int fibonacci (int n); // Calculates the n'th fibonacci number

// main function
int main (void) {
	int n = 1337;
	printf ("Fibonacci Number Calculator - Tolga Ay - 13011057\n\n\n\nEnter a negative number or zero to quit.\n\n");

	while (1) {
		printf ("\nEnter the n to calculate the last fibonacci number of n terms : ");
		scanf ("%d", &n);

		if (n < 1)
			return 0;

		printf ("-> %d", fibonacci (n));
	}
}


// fibonacci function - Calculates the nth fibonacci number
int fibonacci (int n) {
	// We dynamically allocate a fibonacci number array
	// to save the ones we calculated for first time,
	// so we can use that whenever we need the one we already calculated.
	static int* fib = NULL; // Static dynamic array pointer to keep fibonacci numbers
	static int maxN = 0; // The maximum n the function saw, also max length of the array

	// If the dynamic array is not allocated yet, or user entered a number which is bigger
	// than the previous n,
	if (!fib || n > maxN) {
		maxN = n; // Set the new n as maximum N

		if (fib) // If new n is bigger, we need to free the memory and reallocate the fib
			free (fib);

		fib = (int*) calloc (n + 1, sizeof (int)); // Allocate the memory
	}

	// First and second fibonacci numbers are 1, simply return 1
	if (n < 3)
		return 1;
	/*     ---The alternative code snippet for "else if(n < 3)"---
	         We don't free the memory when after the function ends,
	       because user might use it again so we still keep the
	       fibonacci numbers, but however, if you want to free
	       the memory for every calculation, you need to use this part
	       instead of "else if(n < 3)".

	    else if(n == 2)
	        return 1;
	    else if(n == 1){
	        free(fib);
	        return 1;
	    }

	*/
	// If we didn't calculate the fibonacci number, calculate it and return it
	// Else if it's already in our collection, pass the calculation part and
	// return the one we saved to our array before.
	else if (!fib[n])
		fib[n] = fibonacci (n - 1) + fibonacci (n - 2);

	return fib[n];
}