Select Page

# Recursion: Optimization

by | Jul 3, 2017

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.)

## BASIC IDEA

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

return (fibo(n-1)+fibo(n-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.

## IMPLEMENTATION

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.

int cache[16]

main()

{

n=…//input

for(i=1 to n)   //initialising array indexes with not-possible output

cache[i]=0;

cache[1]=1;   //storing basic results OR base case results

cache[2]=2;

print fibo(n);

}

int fibo(int n)

{

if(cache[n]!=0)                             //If the output has been evaluated previously for the given n

return cache[n];

cache[n]=(fibo(n-1)+fibo(n-2)); //storing result in cache for given n

return cache[n];

}

PRECAUTIONS

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

## Codechef: KMXOR Solution

Codechef May Cook-off 2018: KMXOR editorial with Java implementation.

## Algorithm: Binary Search

Variations of the conventional binary search algorithm are discussed.

## Primality Sieves

Segmented Sieve, Sieve of Sundaram, Sieve of Atkin are discussed here.