Recursion and Memoization (Day 1)

Indrajit MandalIndrajit Mandal
10 min read

Table of contents

Recursion

This is a process in which a function calls itself from within its own code.


//such as
a(){
    a();
}

In this function a() will again call a() function [from inside the code] thus making an infinite loop. This is where its power lies as we could write code for an Infinite set of Objects by only writing a finite line of code. Thus it makes writing codes for certain problems easier.

For example,

We are writing code for an output of 0, 1, 2, 3, 4, 5

  1. By Normal Iteration

     public class IterationExample{
     public static void main(String[] args) {
         int n=0;
         System.out.println(n);
         print1(1);  // here it calls the function of print1
     }

     static void print1(int n)
     {
         System.out.println(n);
         print2(2);  // Similarly, here it calls the function of print2
     }

     static void print2(int n)
     {
         System.out.println(n);
         print3(3);  // Similarly, here it calls the function of print3
     }

     static void print3(int n)
     {
         System.out.println(n);
         print4(4);  // Similarly, here it calls the function of print4
     }

     static void print4(int n)
     {
         System.out.println(n);
         print5(5);  // Similarly, here it calls the function of print5
     }

     static void print5(int n)
     {
         System.out.println(n);
     }  // here it simply execute the code.
 }

  2. By Recursion

     public class RecursionExample {
     public static void main(String[] args) {
         print(0);  //calling the function of print()
     }

     static void print(int n)
     {
         if(n==5)  //'if' is used to stop the function otherwise it will enter infinte loop.
         {
             System.out.println(n);
             return;
         }
         System.out.println(n);
         print(n+1);  // it is an recursion as it is ca.lling back the function
     }
 }

Now, it is evident that Recursion is a boon and can decrease our code size by a lot if used correctly.

Factorial

So, What is Factorial?

Factorial is a mathematical function usually represented by n! which is equal to

n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)..................... till 1

For eg. 5!=5*4*3*2*1

Exception - 0!=1

  1. So let's first print 6 factorials by Loop method.

     //6! = 1*2*3*4*5*6
 public class ByLoop {
     public static void main(String[] args) {
         int num = 6;   //num!
         int result = fac(num);
         System.out.println(result);  //will print the value of num!
     }

     static int fac(int num)
     {
         int value = 1;
         for(int n=1;n<=num;n++)
         {
             value= value*n;
         }
         return value;
     }
 }

  2. now by recursion method

     //6! = 6*5*4*3*2*1
 //6! = 6*5!
 //whereas 5! = 5*4!
 //so we can say, n! = n * (n-1)!
 public class ByRecursion {
     public static void main(String[] args) {
         int num = 6;   //num!
         int result = fac(num);
         System.out.println(result);  //will print the value of num!
     }

     static int fac(int num)
     {
         if(num==1) //in order to prevent n-1 becoming 0 or negative
         {
             return 1;
         }
         return num * fac(num-1); //fac(num-1) uses the recursion method
     }
 }

Fibonacci

The Fibonacci sequence is a type of series where each number is the sum of the two that precede it. It starts from 0 and 1 usually. Fibonacci seq. = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on

So Fibonacci no. for the 6th place(Note- starting the count from 0) = 8. Let's find this with the help of code.

  1. By loop

     public class FiboByLoop{  
     public static void main(String[] args) 
     {
         int pos = 6; //here pos is position
         int result = fib(pos); //calling the function fib
         System.out.println(result);  //fibonacci no. on that position
     }

     static int fib(int pos)
     {
         int a=0;  //at 0th position
         int b=1;  //at 1st position
         int c=0;
         for(int i=2; i<=pos; i++)
         {
             c = a+b;
 // 0 1 1 2 3 5 8 13 21 34......
 // a b c(Here we are showing where after executing c=a+b a,b,c are pointing on the above given value)
             //shifting the a and b value to the next position
             a=b;  
             b=c;
         }
         return c; 
     }
 //after the loop ends a,b, c will point
 // 0 1 1 2 3 5 8 13 21 34......
         // a b c
 //so at return c==8
 }

  2. By Recursion

     public class FiboByRecu{  
     public static void main(String[] args) 
     {
         int pos = 6;
         int result = fib(pos);
         System.out.println(result);
     }
 //as we know that fib at 6th position is equal to fib value at 5th and 4th position. So, we can say that fib(n) = fib(n-1) + fib(n-2)
     static int fib(int pos)
     {
         //we know the value of first 3 position
         if(pos==0)
             return 0;
         if(pos==1 | pos==2)
             return 1;

         return fib(pos-1) + fib(pos-2);  // here this are the recursive function
     }
 }

    Now, if we want to print the Sequence itself through Fibonacci, the code will be

       public class FiboSeq{  
     public static void main(String[] args) 
     {//as we can get fib(pos), so just put pos in a loop from 0 to 6 and thus we will get the series.
         for(int pos=0;pos<=6;pos++)
         {
             int result = fib(pos);
             System.out.println(result);
         }

     }

     static int fib(int pos)
     {
         if(pos==0)
             return 0;
         if(pos==1 | pos==2)
             return 1;

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

Memoization

Memoization is the process of remembering or memorizing the value getting from a recursive function to reduce the recursive call of the same number that it has called earlier only.

                            fib(6)   
                     /                 \        
               fib(5)                  fib(4)   
             /      \                /       \
         fib(4)      fib(3)         fib(3)    fib(2)
        /   \          /    \       /      \     |     \
  fib(3)   fib(2)  fib(2) fib(1) fib(2) fib(1)  fib(1) fib(0)
  /    \ 
fib(2) fib(1) 

In the above tree fib(4), fib(3), fib(2), fib(1), fib(0) all are called more than once.

So, using recursion on the same number multiple times, we could simply store the value and use it when needed.

So, it is called by using the Hashmap which in Java stores the data in (Key, Value) pairs, and you can access them by an index of another type such as int. Here, the Key is the index while 'value' is used to store the index's value.

java.util.HashMap is the package for calling HashMap

private static Map<Integer,Integer> cache = new HashMap<>();

Fibonacci with Memoization

Now let's use the Memoization that we learn in Fibonacci Sequence.

import java.util.HashMap;
public class ByLoop {
    private static Map<Integer,Integer> cache = new HashMap<>();
    //cache is a name given by us to call Map
    public static void main(String[] args) {
        for(int pos=0;pos<=6;pos++)
        {
            int result = fib(pos);
            System.out.println(result);
        }

    }

    static int fib(int pos)
    {
        if(pos==0)
            return 0;
        if(pos==1 | pos==2)
            return 1;
        if(cache.containsKey(pos)) //this condition that if there is a same pos value in the cache then return,
            return cache.get(pos); //it is returning pos value stored in result.

        int result=fib(pos-1) + fib(pos-2);
        cache.put(pos, result);  //it is to catch the key pos and store its value as result.

        return result;
    }
}

Assignment

The assignment was to print out the Pascal Triangle by using Iteration, Recursion, Memoization

So, let's do it then

Iteration

import java.util.ArrayList;
import java.util.List;

public class PascalByIteration {
    public static void main(String[] args) {
        int maxHeight = 7;

        List<List<Integer>> answer = new ArrayList<>();
        for (int i = 0; i < maxHeight; i++) 
        {
            List<Integer> col = new ArrayList<>();
            for (int j = 0; j <= i; j++) 
            {
                if (j == 0 || j == i) 
                    col.add(1);

                else 
                    col.add(answer.get(i - 1).get(j - 1) + answer.get(i - 1).get(j));
            }
            answer.add(col);
        }

        for (List<Integer> row : answer) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }
}

This Java program generates Pascal's Triangle using a list-based approach(Iterative). Here's a simplified explanation of the steps involved:

  1. Set the maximum height of the triangle: In the main method, the variable maxHeight is initialized to 7, which determines the number of rows in Pascal's Triangle.

  2. Initialize the list to store the triangle: The program creates an empty list of lists called answer, which will store the values of Pascal's Triangle.

  3. Iterate through each row: A for loop is used to iterate through each row of the triangle. The loop variable i starts from 0 and goes up to maxHeight - 1.

  4. Create a list for the current row: Within the outer loop, a new list col is created to represent the current row of Pascal's Triangle.

  5. Iterate through each column in the row: Another for loop is used to iterate through each column in the current row. The loop variable j starts from 0 and goes up to i (the current row number).

  6. Calculate the cell value: Inside the inner loop, an if-else statement checks if the current column is either the first column (j == 0) or the last column (j == i). If it is, the value 1 is added to the current row col. Otherwise, the value is calculated by summing the corresponding elements from the previous row (answer) at indices j-1 and j.

  7. Add the row to the triangle: After calculating all the values in the current row, the list col representing the row is added to the answer list, which stores the entire triangle.

  8. Print the triangle: Finally, a nested for-each loop is used to iterate through each row in the answer list and print the values of Pascal's Triangle to the console.

By following this process, the program generates Pascal's Triangle with the specified number of rows and prints it to the console using a list-based approach. Each number in the triangle represents a combination of the row and column it belongs to.

Recursion

public class PascalByRecursion
{
    public static void main(String[] args)
    {
        int maxHeight = 7;
        //so as indexing starts from 0 the max value of i is 6.
        for(int i=0;i<maxHeight;i++)
        {
            for(int j=0;j<=i;j++)
            {
            System.out.print(pattern(i,j)+" "); //it is calling the pattern method
            }

            System.out.println();
        }
    }

    static int pattern(int rownum, int colnum)
    {
        if (colnum==0||colnum==rownum) //if colnum=1or colnum=rownum then it will give 1
            return 1;

        int k = pattern(rownum-1,colnum-1)+pattern(rownum-1,colnum); 
        return k;
    }
}

This Java program generates Pascal's Triangle using a Recursive approach. Here's a simplified explanation of the steps involved:

1. Set the maximum height of the triangle: In the main method, the variable maxHeight is initialized to 7. This determines the number of rows in the triangle. We could also use Scanner and nextInt() if we want to take value from the user.

2. Iterate through each row: A for loop is used to iterate through each row of the triangle. The loop variable i starts from 0 and goes up to maxHeight - 1.

3. Iterate through each column in the row: Within the outer loop, there is another for loop that iterates through each column in the current row. The loop variable j starts from 0 and goes up to i (the current row number).

4. Printing the pattern: The System.out.print statement is used to print the value returned by the pattern method. The pattern method calculates the value of the current cell based on its row and column numbers.

5. Moving to the next line: After printing all the values in a row, the System.out.println statement is used to move to the next line, creating the triangular shape.

6. Implementing the pattern method: The pattern method is a recursive function that calculates the value of a specific cell in Pascal's Triangle.

7. Base cases: The if statement checks if the column number (colnum) is either 0 or equal to the row number (rownum). In these cases, the method returns 1, as these are the boundary cells of the triangle and their values are always 1.

8. Recursive calculation: If the column number is not a boundary case, the method recursively calls itself twice, passing the row number decremented by 1 and the column number decremented by 1 for the first call, and passing the row number decremented by 1 and the same column number for the second call. The two values returned by the recursive calls are added together and stored in the variable k.

9. Returning the calculated value: The value of k is returned as the final value of the current cell in Pascal's Triangle.

By following this process, the program generates Pascal's Triangle with the specified maximum height and prints it to the console. Each number in the triangle represents a combination of the row and column it belongs to.

Memoization

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

public class PascalByMemoization
{
    private static Map<String,Integer> cache = new HashMap<>();
    public static void main(String[] args)
    {
        int maxHeight = 7;
        //so as indexing starts from 0 the max value of i is 6.
        for(int i=0;i<maxHeight;i++)
        {
            for(int j=0;j<=i;j++)
            {
            System.out.print(pattern(i,j)+" "); //it is calling the pattern method
            }

            System.out.println();
        }
    }

    static int pattern(int rownum, int colnum)
    {
        if (colnum==0||colnum==rownum) 
            return 1;

        String call = "("+rownum + "," + colnum + ")"; //will be the key
        if(cache.containsKey(call))
        {
            return cache.get(call);
        }

        int k = pattern(rownum-1,colnum-1)+pattern(rownum-1,colnum); //value
        cache.put(call, k);
        return k;
    }
}

Here the basic difference is that we have introduced caching which will get stored thus the code doesn't have to produce the same result again. Thus improving performance and reducing meaningless calculations again and again.

Conclusion👨‍🏫👍

Yeah!!!!! It was my first blog which exceed 2000 words. But learnt quite a new and fun thing. But.....

Again thanks for joining me today, guys! 🙌 I hope you learned something new from my tech blog. 🤓 Until next time, take care and keep exploring the amazing world of technology! 🚀💻.

Also, give a heart button if u like it.😁

0
Subscribe to my newsletter

Read articles from Indrajit Mandal directly inside your inbox. Subscribe to the newsletter, and don't miss out.

JavaRecursionteluskoMemoization

Written by

Indrajit Mandal
Indrajit Mandal

👋 Hey there, tech enthusiasts! I'm a newbie programmer who recently took the plunge and started my journey into the exciting world of coding.🚀 🌎I've created this profile to connect with like-minded learners from all over the world and share my experiences as I explore new technologies and navigate the challenges of this ever-evolving field.💻 🤓Through my posts, you can expect to find insights, tips, and probably a few embarrassing mistakes along the way (hey, we all have to start somewhere!). But what's even better is that we'll be doing it together - building a community of explorers and learners who are passionate about pushing the boundaries of what's possible with technology.🤝 So if you're ready for a journey of discovery, laughs, and learning, come join me and let's see where this wild ride takes us!🤗