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

One thought on “Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative )

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s