Recursion and Dynamic Programming

Recursion

Recursion is nothing more than re occurring. Yes I know it sounds crazy, but there is nothing more to it.

Even before we jump into coding let me explain how recursion is implemented by the operating system. When we call the same function again, it stores all the variables in the current session on a stack and moves on to the next level of function, calling the function again results in the same operation again.

Please refer to memory management section of this blog, which explains the concept of stack memory. If it is still not clear let me know and I will add more explanation.


Now let us take a simple example of fibonacci number series. If you are not aware click here.

1 1 2 3 5 8 13 ....

So one can generalize it as any t(n) = t(n-1) + t(n-2).

If we want to print a fibonacci series unto n, we only repeat the formula above n times. Since we are repeating the same formula n time we call it re occurrence, that is recursion.

Now how do we write the code for the same.

http://codepad.org/oypkKADM 

In the code above we are repeatedly calling the same function so the same recursion. 

Can you spot what is wrong in this algorithm ? 

We calculate the t(0) for all the indexes for 0, 1, 2, 3, 4 and so on.

Do we need to calculate that every time ? Can we do better ? Yes we can and that is called dynamic programming.

Dynamic Programing : 

Dynamic programing uses caching in recursive programing. To make it more clear dynamic programing is technique in which it remembers what it did in its previous function call, so that it need not do the same again. For the same example above we can store the values of t(n), so that we can use it to calculate the next t(i).

Lets see code example,

http://codepad.org/1O4ydqP7

As you can see it is no different than recursive programing other than remembering all the calculated values. That is dynamic programing.

1) Imagine a staircase with n steps, you can hop either 1,2 or 3 steps at a time, implement an algorithm to find the number of ways you can climb up the stairs.
A) This is similar to Fibonacci series we discussed earlier. The base case here would be n < 0 we return a 0 and if n == 0 we return a 1.

To be more precise the last step n could be reached from step n-1 or step n-2 or step n-3.

The total number of ways of reaching n is the sum of the number of ways of reaching n-1, n-2, n-3.

Lets see the code

http://codepad.org/rmr7cB0B

If you see the code it is pretty straight forward, you add up all the possible ways of reaching n by summing all the 3 possible ways at each step.

Just like the fibonacci series even here we have repeated calculations. We can reduce the same using dynamic programing.

Can you try the code yourself ?

If not here it is

http://codepad.org/nuTIK1n9

2) Given two strings print the longest common subsequence.

A) We need to first identify the length of the longest common subsequence and then back track the actual sequence.

Lets take the example of "AGGTABC" and "GXTXAYBC".

Let one string be a row in a 2 dimensional matrix and the other be the column.

The figure below explains it better

The main idea here is to consider each character as a string and find the length of the longest common sub sequence. i.e consider G as a string and A as a string and the length of longest common sub sequence which is 0. In the same way we continue with the rest of the string which is "G" and "AG" then "G" and "AGG".

The logic comes to be if both the characters are same we add one to diagonally previous cell. That is G in column string is same as the first G in row string we add 1 to zero below A. If the characters are not same we get the maximum among the cell above it and the cell beside its left.

Now lets consider how to trace the actual substring.

We need to back trace where ever we had a same character we copy that one into the result.

As can be seen the picture above we copy a character as we move diagonally above in the matrix.

The code below is the code to implement the same.

http://codepad.org/PsjXzVdP

3) Given an unsorted array find the length of longest increasing sub sequence.

A) The first approach is to iterate the entire array and at each element calculate the longest increasing sub sequence until then and store it in another array called Temp.

The maximum number in Temp is the result.

For example :  Array = {3, 4, -1, 0, 6, 2, 3}

                        Temp  ={1, 1, 1, 1, 1, 1, 1}

Each element in Array by itself is the longest increasing sub sequence, i.e if we have just {3} that itself is the longest increasing sub sequence of length 1. Hence we initialize all the elements in Temp with 1.

Now we loop through each and every element in Array and calculate the length of longest subsequence until that index using the formula below
     
                        if(Array[j] < Array[i])
                         Temp[i] = Max(Temp[j] + 1, Temp[i])

Where i is the index of outer loop and j is the index of inner loop.

The following is the code in C#.

The computational complexity of this algorithm is O(N^2)


Can we do better ?

Yes we can, we only need the last element in any sub sequence, so we store the last elements of all the longest sub sequences while iterating the main array. The main logic in this approach is to discard sub sequences which could lead to smaller subsequences.

Here is the code for you in C#

The binary search algorithm is used to search for an element which is greater than the key element, once found it will be replaced with the smaller one.

Now comes the main algorithm