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; }
One thought on “Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative )”