Recursion and Memoization in Java - Examples and Implementation

Recursion

A recursive function is a special type of function that calls itself, which allows for the breakdown of complex problems into smaller, more manageable problems. This approach is commonly known as a recursive approach.

Base Condition

The base condition, a check on the function that prevents it from repeating forever is the most crucial part of a recursion function. Without it, a stack overflow error will occur.

This code calculates the factorial of a given number using recursion.

 public static void main(String[] args) {
        fact(5);
    }
    public static int fact(int n){
        //base condition
        if(n==1){
            return n;
        }
        return n*fact(n-1);
    }        

This code finds the fibonacci number at a given position using recursion.

public static void main(String[] args){
        fib(9);
    }

    public static int fib(int n) {
        
        //base condition

        if (n < 2) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);
    }        

Downside of using Recursion

1. Bad Space and Time complexity
2. Hard to understand and Debug
3. Redundant computations

In the above diagram, we can see that the recursive function is being executed multiple times for the same inputs that have already been computed and processed. Specifically, the function fib(1) is being invoked five times. This can be improved through the process of Memoization.

Memoization

We've shown that the issue of repeated computation over the same problems but if we temporarily store computation values and discontinue unnecessary computation, recursion issues can be reduced and time complexity can be increased , this is known as Memoization or memorizing the values temporarily

It usually requires a data structure, mostly hashmaps, which saves the data as key and value.

This function stores each recursion value and then check it by key value and if it is present in hashmap it gives the value rather than doing computation again.

public static int fibonacci(int n) {

        if (cache.containsKey(n)) {
            return cache.get(n);
        }


        int result;

        if (n <= 1) {
            return n;
        } 

        else {
            result = fibonacci(n - 1) + fibonacci(n - 2);
        }

        cache.put(n, result);
        return result;
    }
        

Assignment Question (Telusko)

Write a Program on printing Pascal triangle using iteration , Recursion and Memoization

Pascal Triangle with Iteration

Github Link

    int[][] triangle = new int[n][]
          for (int i = 0; i < n; i++) {
              triangle[i] = new int[i + 1];
              triangle[i][0] = 1; // first element in each row is always 1
              
              for (int j = 1; j < i; j++) {
                  triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
              }
              
              triangle[i][i] = 1; // last element in each row is always 1
          }
          
          // Printing

          for (int i = 0; i < n; i++) {
              for (int j = 0; j <= i; j++) {
                  System.out.print(triangle[i][j] + " ");
              }
              System.out.println();
          };        

We observe that every first element of the pascal triangle is 1 and ends with 1 , so we initiate the matrix with 1 and then the first loop calculate the value of middle elements by adding the above two values triangle[i - 1][j - 1] + triangle[i - 1][j] using this logic, then we initiate the last element as 1 also.

Pascal Triangle with Recursion

GithubLink

    public static void main(String[] args) {
        int n = 5;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(calue(i, j) + " ");
            }
            System.out.println();
        }
    }
    
    public static int cal(int row, int col) {
        if (col == 0 || col == row) {
            return 1; // first and last element in each row is always 1
        } else {
            return cal(row - 1, col - 1) + cal(row - 1, col);
        }
    }        

Here we use the similar approach , as we know pascal triangle start and ends with 1 so we make the base condition return 1 and we use the same logic to calculate the values by adding the above.

Printing pascal triangle using the Memoization

Github Link

import java.util.HashMap
import java.util.Map;


public class PascalTrianglecacheization {
    private static Map<String, Integer> cache = new HashMap<>();


    public static void main(String[] args) {
        int n = 5;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(calculate(i, j) + " ");
            }
            System.out.println();
        }
    }
    
    public static int calculate(int row, int col) {
        String key = row + "-" + col;
        
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        
        if (col == 0 || col == row) {
            cache.put(key, 1);
        } else {
            int value = calculate(row - 1, col - 1) + calculate(row - 1, col);
            cache.put(key, value);
        }
        
        return cache.get(key);
    }
}

;        

Here we store our computation values in a data structure ( hashmap in java)

which stores the values of calculation (row , column) if the value of this index already exist in the cache it will not compute again and just give us the answer.

we use the same logic above in recursion if base condition got hit it will give 1 because it start and ends with 1 and will calculate the values in between using the approach we used above Matrix [row - 1][column - 1] + Matric[row - 1][column].

Conclusion

I have learned about generating Pascal's triangle using Java. Through the examples provided, I was able to understand the iterative, recursive, and memoization approaches for creating Pascal's triangle. By exploring and modifying the code, I gained a deeper understanding of the underlying concepts.

Thank You Navin Reddy and team for the task.