Recursion usually is preferred to solve complex problems easily. However, sometimes it leads to unnecessary reevaluations/calculations. This article shall discuss one of the ways to optimize recursive codes, namely Memoization. (If you are new to recursion, do check out this article.)
Sometimes a function might be called multiple times for the same inputs. In such cases, rather than reevaluating the value of the function, we can reuse the output calculated previously for the same input.
To implement this, we store the output for the input at each function call. Also, at every function call, we check whether the value of the function has been evaluated for that particular input previously. If yes, we return the stored value, else we evaluate the result, store it and return it. This technique is called memoization.
Here is an example to explain. Consider the recursive pseudocode evaluating the nth Fibonacci number:-
int fibo(int n)
if(n==1)return 1; //F(1)=1 base case #1
if(n==2)return 1; //F(2)=1 base case #2
Suppose the user calls the function fibo(7), fibo(7) calls fibo(6) and fibo(5), fibo(6) calls fibo(5) and so on. Here is a flowchart to depict it:-
Clearly, we see that the function fibo(3) is called 5 times and each time its value is reevaluated. This adds unnecessary computation and can be optimized using the above technique.
We need to add two things to our code:
(1) A way to check whether the value has been previously evaluated
(2) A way to store the result for new inputs
(2) can be implemented easily by storing the result in an array after evaluating and before returning. Suppose the return value of a function is of integer datatype and the input ranges from 0 to 10000. We define an integer array cache of size 10001 such that cache[i] stores the result for input i.
However,(1) can be implemented using two ways:-
(a) We define a boolean array to store whether the result for the given array has been evaluated. In the beginning, all indexes are marked false. Every time the function is called, we check if the index is marked or not. If it is marked, we return the value stored for that input. Else we evaluate the result, store it and mark the index for the given input as true.
(b) We initialise all indexes of the storage array(cache) with a value which cannot be the output of the function(such as a negative number for the Fibonacci sequence).
With that in mind, let us implement the optimized recursive pseudocode for the Fibonacci sequence for 1<=n<=15.
for(i=1 to n) //initialising array indexes with not-possible output
cache=1; //storing basic results OR base case results
int fibo(int n)
if(cache[n]!=0) //If the output has been evaluated previously for the given n
cache[n]=(fibo(n-1)+fibo(n-2)); //storing result in cache for given n
1. Memoization takes up a lot of space and is usually used to reduce computational time by a compromise of space.
2. One must check the constraints before implementing memorisation. Usually a 1-D array of size<=10^6 can be used for memorization with ease.
Sometimes, dynamic programming provides a more optimized implementation while maintaining the recursive logic. We shall discuss this in upcoming articles.
More from this Category
Insight on building a software.
Codechef May Cook-off 2018: KMXOR editorial with Java implementation.
Variations of the conventional binary search algorithm are discussed.
This article explains breadth first traversal and depth first traversal in graph theory.
Terminology and methods to represent a graph are explained.
Segmented Sieve, Sieve of Sundaram, Sieve of Atkin are discussed here.