Usually, most of the programmers (poor ones like me :p) think iteratively to solve a problem. This works, until you get a problem which is expected to be solved recursively or even worse what if non-recursive solution is bit tricky. Take a classic example of binary tree traversal, it's a breeze if it needs to be done recursively (just few lines would do the job). You are not going to always get such commonly occurring or well known problems. What if you land to a brand new problem to be solved recursively? How you going to check if recursion can be applied or not ?
Your ability to come up with multiple solutions to a problem will be limited if you don't try to come up with recursive solution. It takes time to develop the recursive thinking, and ofcourse with lots of persistent hard work.
Your ability to come up with multiple solutions to a problem will be limited if you don't try to come up with recursive solution. It takes time to develop the recursive thinking, and ofcourse with lots of persistent hard work.
Let's go through some of the fundamental aspects which can be invaluable to develop recursive thinking (cap). In this post, I will cover recursion, rules for solving a problem recursively and finally explain the concept through couple of problems.
Recursion
Recursion is another approach to solve problems which require repetition. Problem is solved by reducing it to a smaller problem of the same kind. This process is continued until we reach to a very small problem (base case) which can be solved directly. Base condition stops the further method call.
Let's start with a simple problem of printing all numbers between two given numbers(both inclusive).
//Java Implementation
public void print(int a, int b){
if(a == b){
System.out.println(a);
return;
}
else{
System.out.println(a);
print(a+1, b);
}
}
Above recursive algorithm reduces the problem to a smaller problem in each call (until base condition is reached). So, print(2,5) becomes print(3,5) after first call and so on until both a and b are same.
print(2,5)
-->print(3,5)
-->print(4,5)
-->print(5,5) //base case
Basic idea in recursion is to reduce problem to smaller problem of the same kind.
Recursive Thinking
Developing recursive thinking is about your ability to ask few (important) questions for solving any problem.
- How can the problem be broken down to one or more subproblems (smaller problem)?
- What is the base case?
- Does each subproblem has a (partial) solution? How that should be combined to get final result?
You need to have answer to all questions to solve a problem. Over a period of time, this pattern becomes very obvious and smart programmers can find it quite easily. You need to practice a lot to make recursive thinking part of your (algorithmic) problem solving toolkit.
Let's apply recursive thinking on above method, print(a,b) -
- Problem can be broken down to smaller subproblem - Yes. Print first argument and then print all numbers between first argument + 1 and second argument.
- Base case - print numbers until first argument becomes second argument (i.e. a==b)
- Does each subproblem has a solution -No. They just print the value on console so there is no intermediate answer or partial solution.
Problems
Let's apply recursive thinking on few problems. I will use RT#1, RT#2, RT#3 to look for valid answer to the three Recursive Thinking questions:
p1: Find the length of a string
RT#1: How can this problem be divided into subproblems? So instead of finding length of complete string, can we find length of a smaller string to somehow get the full length ?
length("abc") = can we find the full length if we know, length("bc")
or, length("abc") = can we find the full length if we know, length("ab")
RT#2: Base case is something whose answer we already know.
length("") = 0
or, length("a") = 1
RT#3: Yeah subproblem has a solution.
length("abc") = 1 + length("bc")
or, length("abc") = 1 + length("ab");
algorithm:
int length(str){
if(str.hasOneChar())
return 1;
else
return 1 + length(str.substring(1));
}
p2: Compute power(X,n) (i.e. X^n = X*X*X.....*X, n of them)
RT#1: Quite clear, power(X, n-1) can be one of the subproblem (let's stick with this for now).
RT#2: Base case, n = 0 then power(X,n) would be 1
RT#3: X^n = X* X^(n-1)
algorithm:
int power(x,n){
if(n == 0)
return 1;
else return x*power(x,n-1);
}
Complexity of above problem = O(n). Subproblem reduces the length by 1 in each call.
Above is a legitimate recursive solution, but it can be improved to a better recursive solution with complexity of O(log n). Can we reduce size of problem to half in each recursive call (something like binary search) ?
algorithm:
int power(x,n){
int power(x,n){
if(n == 0)
return 1;
else
int p = power(x,n/2)
if ( n is even ) return p*p;
else x*p*p;
}
Backtracking: http://www.thegeekstuff.com/2014/12/backtracking-example/
Do post your feedback below.
---
think recursion, thank recursion !!!
keep coding !
keep coding !
No comments:
Post a Comment