What is Recursion and Memoization in Java ? - Learn With AVRK

Recursion: Recursion is a programming technique where a function calls itself repeatedly to solve a problem by breaking it down into smaller subproblems. In a recursive function, the function is defined in terms of itself. Each recursive call works on a smaller portion of the problem until a base case is reached, which is a condition that stops the recursion.

When using recursion, a problem is divided into simpler, similar subproblems. The recursive function solves each subproblem independently and combines their results to solve the original problem. Recursion is especially useful for solving problems that exhibit a recursive structure, such as traversing hierarchical data structures or performing computations on recursive sequences.

Memoization: Memoization is a technique used to optimize recursive algorithms by caching (or memoizing) the results of expensive function calls. It avoids redundant computations by storing the results of function calls in a data structure, such as a map , so that the values can be directly retrieved if the function is called again with the same arguments.

The memoization technique helps to improve the performance of recursive algorithms, as it eliminates duplicate computations and reduces the time complexity. By storing previously computed values in memory, subsequent function calls with the same arguments can be resolved in constant time.

In Java, memoization is often implemented using a map data structure, where the function arguments are used as keys and the computed values are stored as corresponding values in the map. Before performing a computation, the function checks if the result for the given arguments is already memoized in the map. If it is, the cached result is returned instead of recomputing it. If it is not memoized, the function performs the computation, stores the result in the map, and returns it.

I am attaching github link to see example of Java program that prints Pascal's Triangle using recursion and memoization concept.

Here's a breakdown of how the code works:

1. The program imports the necessary classes from the java.util package: HashMap and Map.

2. The Main class is defined.

3. Inside the Main class, a static memo map is declared to store the computed values of coefficients for each combination of row and column.

4. The main method is the entry point of the program. It initializes the variable row with the desired number of rows to print.

5. The program then enters a loop that iterates from 0 to row - 1 to handle each row of the triangle.

6. Within the loop, the program first prints a number of spaces to align the triangle properly. The number of spaces is equal to row - i, where i is the current row index.

7. Next, there is an inner loop that iterates from 0 to i to calculate and print the coefficients for the current row.

8. Inside the inner loop, the Coefficient method is called with the current row i and column j as arguments. The returned coefficient value is stored in the cof variable.

9. The coefficient value is then printed, followed by a space.

10.  After the inner loop completes for a row, a new line is printed to move to the next row.

11. The Coefficient method is a recursive function that calculates the coefficient value for a specific row and column.

12. The method first checks if the column is 0 or equal to the row. In such cases, the coefficient value is 1, so it returns 1.

13. If the coefficient value for the given row and column is already memoized in the memo map, it is directly returned from the map.

14. If the coefficient value is not memoized, the method recursively calls itself for the two previous rows and columns, and then adds those two values together to calculate the coefficient.

15. The calculated coefficient value is memoized by storing it in the memo map with the key being a string representation of the row and column.

16. Finally, the calculated coefficient value is returned.

Overall, the program uses recursion and memoization to efficiently compute the coefficients of Pascal's Triangle and prints them in the desired format. The memoization technique helps avoid redundant calculations and improves performance by storing previously computed values for reuse.

Also check out this : What is Firewall in Computer Network - Learn With AVRK