Difference between Recursion and Dynamic Programming

Recursion and Dynamic programming are two effective methods for solving big problems into smaller, more manageable subproblems. Despite their similarities, they differ in some significant ways.

Below is the Difference Between Recursion and Dynamic programming in Tabular format:

Let's take an example: Find out the N^th Fibonacci number

1) Using Recursion:

Below is the code of Fibonacci series using recursion:

#include <iostream>

int fibonacci_recursive(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    }
}

int main() {
    int n = 5;
    int result = fibonacci_recursive(n);
    std::cout << result << std::endl;
    return 0;
}

public class GFG {
    // Recursive function to calculate the nth Fibonacci number
    public static int fibonacciRecursive(int n) {
        if (n <= 1) {
            // Base case: Fibonacci of 0 is 0, and Fibonacci of 1 is 1
            return n;
        } else {
            // Recursively calculate Fibonacci for n-1 and n-2
            return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int result = fibonacciRecursive(n);

        System.out.println(result);
    }
}

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

print(fibonacci_recursive(5))

using System;

public class Solution
{
    public int FibonacciRecursive(int n)
    {
        if (n <= 1)
        {
            return n;
        }
        else
        {
            return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
        }
    }

    static void Main()
    {
        Solution solution = new Solution();
        Console.WriteLine(solution.FibonacciRecursive(5));
    }
}

function fibonacciRecursive(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }
}

const n = 5;
const result = fibonacciRecursive(n);
console.log(result);

5

Time Complexity: O(2ⁿ), which is highly inefficient.
Auxiliary Space: Recursion consumes memory on the call stack for each function call, which can also lead to high space complexity. Inefficient recursive algorithms can lead to stack overflow errors.

2) Using Dynamic Programming:

Below is the code of Fibonacci series using Dynamic programming:

#include <iostream>
#include <vector>

int fibonacci_dp(int n) {
    std::vector<int> fib(n + 1, 0);
    fib[1] = 1;

    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    std::cout << fibonacci_dp(5) << std::endl;

    return 0;
}

import java.util.Arrays;

public class FibonacciDP {

    static int fibonacciDP(int n) {
        int[] fib = new int[n + 1];
        fib[1] = 1;

        for (int i = 2; i <= n; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacciDP(5));
    }
}

def fibonacci_dp(n):
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

print(fibonacci_dp(5))

using System;

class Program
{
    // Function to calculate the nth Fibonacci number using dynamic programming
    static int FibonacciDP(int n)
    {
        // Create an array to store Fibonacci numbers
        int[] fib = new int[n + 1];
        
        // Initialize the first two Fibonacci numbers
        fib[1] = 1;

        // Calculate Fibonacci numbers from the bottom up
        for (int i = 2; i <= n; ++i)
        {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        // Return the nth Fibonacci number
        return fib[n];
    }

    static void Main()
    {
        // Test the FibonacciDP function with n = 5
        Console.WriteLine(FibonacciDP(5));
    }
}

function fibonacci_dp(n) {
    const fib = new Array(n + 1).fill(0);
    fib[1] = 1;

    for (let i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

console.log(fibonacci_dp(5));

5

Time Complexity: O(n), a vast improvement over the exponential time complexity of recursion.
Auxiliary Space: DP may have higher space complexity due to the need to store results in a table. In the Fibonacci example, it's O(n) for the storage of the Fibonacci sequence.

Application of Recursion:

• Finding the Fibonacci sequence
• Finding the factorial of a number
• Binary tree traversals such as in-order, pre-order, and post-order traversals.

Application of Dynamic Programming:

• Calculation of Fibonacci numbers and storing the results
• Finding longest subsequences
• To identify the shortest pathways in graphs, dynamic programming techniques like Dijkstra's.

Conclusion:

Recursion and dynamic programming both use common problem-solving techniques, although they focus differently on optimisation and memory usage. The nature of the issue and the intended outcome of the solution will determine which option is best.