Dynamic programming – taking the curse out of recursion!


I think most of the programmers are familiar with recursive code and almost all of us have solved recursive problems like Fibonacci series or Factorial during our CS courses. We know that if try higher numbers, the code crashes with StackOverflowError.

Dynamic programming or DP as it is popularly known is a blessing for many problems requiring either recursive or iterative algorithms. I am not going to go into the details of DP as such, you can easily find good information about it on Wikipedia or read about it in any one of those excellent tutorials available on the Internet, one such example can be found here on CodeChef.

In short, Dynamic Programming is an approach of solving complex problems by breaking them into several smaller sub-problems, where the sub-problems are overlapping sub-problems. It can make lot of recursive problems much more efficient. Dynamic Programming approach is similar to recursive programming, however in dynamic programming the intermediate results are cached/stored for future calls.

If we consider recursive programing for Fibonacci series, – computing the nth number depends on the previous n-1 numbers and each call results in two recursive calls. Thus, the time complexity is –

T(n) = T(n-1) + T(n-2) = O(2n).

In other words, as we increase the Fibonacci number, the time taken to compute that Fibonacci number increases exponentially!

On the other hand, if we use Dynamic Programming for Fibonacci number, since the earlier results are cached, we simply have complexity as –

Time Complexity = O(n)
Extra Space = O(n)

In fact, it is fairly easy to reduce additional space for Fibonacci number by just storing previous two results instead of storing all the previous results.

In plain English, it means that Dynamic Programming can drastically reduce the time taken to compute solutions that require several recursive/iterative calls. As an experiment, I wrote small Java code that computes Fibonacci number using recursion as well as Dynamic Programming. Do watch the results posted below this code to know respective time taken while computing the 50th Fibonacci number. You can try this code with different numbers on your own computer as well and see it for yourself. DP rocks!!! 🙂

public class FiboDyna{
    long fibo[] = new long[200];
	
    public long fibonacci(int n){
	if (0 == n){
		return 0;
	}
	if(1 == n){
		return 1;
	}
	//return result from cache
	if(0 != fibo[n]){
		return fibo[n];
	}
	fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
	return fibo[n];
    }
	
    public long fibonacci_rec(int n){
	if (0 == n){
		return 0;
	}
	if(1 == n){
		return 1;
	}
	return fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
    }	
	
    public static void main(String args[]){
	FiboDyna fd = new FiboDyna();
	long start = System.currentTimeMillis();
	System.out.println("Dynamic fibonacci 50 = " + fd.fibonacci(50));
	long finish = System.currentTimeMillis();
	System.out.println("Time taken for Dynamic Fibbonacci = " 
                            + (finish - start) + " ms");
		
	start = System.currentTimeMillis();
	System.out.println("Recursive fibonacci 50 = " + fd.fibonacci_rec(50));
	finish = System.currentTimeMillis();
	System.out.println("Time taken for Recursive Fibbonacci = " 
                            + (finish - start) + " ms");
    }
}

dp-fibo

I am hoping to use it for some non-trivial, real-life problem whenever I can, and if I manage to do that successfully, I’d definitely post it here!

Advertisements

One thought on “Dynamic programming – taking the curse out of recursion!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s