Fibonacci Sequence using Recursion and Memoization in C language.

Fibonacci Sequence using Recursion and Memoization in C language.

/* Program will break after sum reachs to int holding limit which is around 4 billion*/

/* Usage : gcc -o fib <file.c> --std=c99
  ./fib <number>
*/

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

int recursiveFibonacci(int *cache, int n);
int *cache(int n);
int main(int argc, char const *argv[])
{
    int n = atoi(argv[1]);
    int *memo = cache(n + 1);
    printf("%d\n", recursiveFibonacci(memo, n));
    return 0;
}

int recursiveFibonacci(int *memo, int n)
{

    if (n < 2)
    {
        return n;
    }
    if (memo[n] != -1)
    {
        return memo[n];
    }

    memo[n] = recursiveFibonacci(memo, n - 1) + recursiveFibonacci(memo, n - 2);
    return memo[n];
}
int *cache(int n)
{
    int *cache = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        cache[i] = -1;
    }
    return cache;
}