Recursion and Memoization
The recursive call to a function is one of the methods to solve a problem that is made of many sub-problems. In recursion, the main idea is to find a base sub-problem and use it recursively. E.g Find factorial of 6. We calculate 6! by multiplying 6 with 5!. Calculate 5! by multiplying 5 with 4!. So recursively we can solve factorial of n by calculating n * func(n-1). But while running this program the computer still needs to calculate every factorial. To calculate 6! it will still need to calculate 4! even though we already calculated 4! while calculating 5!. This is time-consuming so we use small memory to store previous calculations. Before doing new calculations first we check if the calculation is already in memory. If it is not, we calculate the result from memory. This is called Memoization. This method is pretty popular for solving Dynamic Programming and Backtracking Problems.
Fibonacci Series with Recursion and Memoization
The Fibonacci Series is a classic problem in programming. It can be solved using recursion and memoization. Following is the python code to solve Fibonacci Series for n using recursion and memoization.
Recursion, implicit memory and Iteration
In the above both codes we use recursion. In the first code, it seems we don’t require extra memory. But that is not true. The computer requires to store partial results in the stack before calculating sub-problems. After calculation, it pops out partial results from the stack and computes results. For Eg for n = 3, the computer pushes fib(3), then it pushes fib(2) and calculates fib(1) which is 1. Then it pops fib(2) from the stack and calculates. Finally, pop fib(3), calculate, and return the result. It does the same even if we use memoization. It is not space-efficient that is why we use iteration. All the recursion problems can be solved as iteration problems. It might get complicated but could be more efficient than recursion. Following is the iteration code of the same Fibonacci Series
Solving Recursion problems
Recursion is a very popular and easiest technique to solve Linked List and Binary Tree problems. Most of the recursion problem can be solved in O(n) time and space complexity where n is the number of nodes. Following are few examples.
Merge Two Sorted Lists
|Merge Two Sorted Lists||11||link|