Recursion & Memoization

Hello connections,

In this article, you will learn about Recursion and Memoization using Java.

Recursion:

Recursion is the technique of making a function call itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

Memoization:

In programming, memoization is an optimization technique that makes applications more efficient and hence faster. It does this by storing computation results in cache, and retrieving that same information from the cache the next time it's needed instead of computing it again.

In simpler words, it consists of storing in cache the output of a function, and making the function check if each required computation is in the cache before computing it.

A cache is simply a temporary data store that holds data so that future requests for that data can be served faster.

Memoization is a simple but powerful trick that can help speed up our code, especially when dealing with repetitive and heavy computing functions.

Ex. Pascal's Triangle:

Pascal's triangle is a triangular array constructed by summing adjacent elements in preceding rows. Pascal's triangle contains the values of the binomial coefficient. It is named after the 17th century French mathematician, Blaise Pascal (1623 - 1662).

1

1 1

1 2 1

1 3 3 1

.....

Construction of Pascal's Triangle

Begin by placing a 1 at the top center of a piece of paper. The next row down of the triangle is constructed by summing adjacent elements in the previous row. Because there is nothing next to the 1 in the top row, the adjacent elements are considered to be 0:

This process is repeated to produce each subsequent row:

This can be repeated indefinitely; Pascal's triangle has an infinite number of rows:

Implementation of pascal's triangle using iteration:

public class PascalTriangle_Iterative {

	    static void pascalTriangle(int n) {
	        int num=1;
	        for (int i = 0; i < n; i++) {
	            num=1;
	            for (int j = 0; j < n-i+1; j++) {
	                System.out.print(" ");
	            }
	
	            for (int j = 0; j <=i; j++) {
	                System.out.print(num+" ");
	                num=num*(i-j)/(j+1);
	            }
	            System.out.println();
	        }
	    }
	
	    public static void main(String[] args) {
	        int n = 5;
	        pascalTriangle(n);
	    }
	}        

Implementation of pascal's triangle using recursion:

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

	        for (int i = 0; i < n; i++) {
	            for (int j = 0; j < n - i + 1; j++) {
	                System.out.print(" ");
	            }
	

	            for (int j = 0; j <= i; j++) {
	                System.out.print(pascalTriangle(i, j) + " ");   
	            }
	            System.out.println();
	        }
	    }
	

	    private static int pascalTriangle(int row, int col) {  
	        if (col == 0 || col == row) {
	            return 1;
	        } else {
	            return pascalTriangle(row - 1, col - 1) + pascalTriangle(row - 1, col);
	        }
	    }
	}        

Implementation of pascal's triangle using memoization:

import java.util.HashMap;
import java.util.Map;
	
	public class PascalTriangle_Memoization {
	

	    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 < n - i + 1; j++) {
	                System.out.print(" ");
	            }
	

	            for (int j = 0; j <= i; j++) {
	                System.out.print(pascalTriangle(i, j) + " ");
	            }
	            System.out.println();
	        }
	    }
	

	    private static int pascalTriangle(int row, int col) {
	        if (col == 0 || col == row) {
	            return 1;
	        }
	

	        String key = row + "-" + col;
	        if (cache.containsKey(key)) {
	            return cache.get(key); // Return cacheized value if it exists
	        } else {
	            int value = pascalTriangle(row - 1, col - 1) + pascalTriangle(row - 1, col);
	            cache.put(key, value); // Store the calculated value in the cacheization map
	            return value;
	        }
	    }
	}        

GitHub Link