Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative )

Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative ) Dynamic Programming:

---

Top Down Fibonacci Memoization Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

#define N 64
long long F[N];

/**
 * Top Down Recursive Fibonacci Memoization
 */
long long topDownMemFib(long long n){
    /**
     * If its not 1 then it means there is already a calculated value
     * So no more need to compute, just return that value
     */
    if(F[n] != -1)
        return F[n];

    F[n] = topDownMemFib(n - 1) + topDownMemFib(n - 2);
    return F[n];
}

int main(){
    register unsigned i;

    unsigned n;
    printf("Enter a number:\n");
    scanf("%u", &n);

    /**
     * Terminating condition values
     */
    F[0] = 0;
    F[1] = 1;

    /**
     * First set the whole array to -1, means there are no calculated value
     */
    for(i = 2; i <= n; ++i)
        F[i] = -1;

    printf("%lld\n", topDownMemFib(n));

    return 0;
}

---

 

Bottom Up Iterative Fibonacci Implementation:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

/**
 * Increase this value for numbers more than 64
 */
#define N 64
long long F[N];

/**
 * Top Down Fibonacci Memoization
 */
long long bottomUpMemFib(long long n){
    /**
     * Terminating Condition
     */
    F[0] = 0;
    F[1] = 1;

    register unsigned i;
    for(i = 2; i <= n; ++i)
        F[i] = F[i - 1] + F[i - 2];

    return F[n];
}

int main(){
    register unsigned i;

    unsigned n;
    printf("Enter a number:\n");
    scanf("%u", &n);

    printf("%lld\n", bottomUpMemFib(n));

    return 0;
}

Advertisements