#include using namespace std; int intN; // we are trying to find out N th number of fibonaci series. This is input int intArrGlobal[100] ;// Array to be used for Dynamic Programming (DP)... initialized to 0 for all elements //Fibonaci series using recursion int getFibonaciUsingRecursion(int intN) { cout << "Debug -> Rec: Fibonaci compute for " << intN << endl; if (intN <=2) // Base case of recursion... First two elements are 0 and 1...Hence, we are using rerurn as zero and one for N = 1 and 2 respectively { return intN-1; } return getFibonaciUsingRecursion (intN -1) + getFibonaciUsingRecursion (intN -2); // Fibonaci number is summation of previous two numbers } //Fibonaci series using DP int getFibonaciUsingDP(int intN) { if(intArrGlobal[intN ] != 0) // check if already computed or not..if computed, directly return value { return intArrGlobal[intN ]; } cout << "Debug -> DP: Fibonaci compute for " << intN << endl; if (intN <=2) // Base case of recursion... First two elements are 0 and 1...Hence, we are using rerurn as zero and one for N = 1 and 2 respectively { // store value for next iterarion intArrGlobal[intN ] = intN -1; return intN-1; } //store value for next iteration intArrGlobal[intN ] = getFibonaciUsingDP (intN -1) + getFibonaciUsingDP (intN -2); return getFibonaciUsingDP (intN -1) + getFibonaciUsingDP (intN -2); // Fibonaci number is summation of previous two numbers } int main() // Main function to call Recursive and DP functions { cin>>intN; // user input int intAnsRecursion = getFibonaciUsingRecursion (intN ); // Recursion call cout << endl << "Output : Fibonaci number at index " << intN << " is "<< intAnsRecursion << endl << endl; // output of recursion int intAnsDP = getFibonaciUsingDP (intN ); // DP call cout << endl << "Output : Fibonaci number at index " << intN << " is "<< intAnsDP << endl; // output of DP return 0; }

DynamicProgramming_Recursion