About Recursion

Recursion is the technique to solve problems by dividing the problem into :

1. A Base Case / Termination Condition.

2. A Sub-Problem / Recursive Call.

3. Combining the results of Sub-Problems to obtain the final result.

Wanna Experience Recursion ? Click the following link …

http://s4sagar.wordpress.com/2009/07/30/about-recursion/

Another funny example for recursion ,

Try googling “recursion”

http://www.google.co.in/search?hl=en&rlz=1C1CHMI_en-USIN307IN308&ei=6ARySvSgB5zW7AOB7oyrCw&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=recursion&spell=1

You will see a “Did  you mean : recursion”

Try clicking “recursion” in “Did you mean: recursion” and you will understand what recursion is

Examples:

1. Factorial Problem

Problem Statement :  To evaluate n !

Recursive Solution :

unsigned int fact ( int n )  {

if( n <= 1 ) return 1;

return n * fact ( n -1 ) ;

}

Terminating Condition /Base Case : n <= 1

Sub-Problem : To evaluate fact( n – 1 )

Final Solution : n * fact ( n  -  1 )

You can see that it combines all the subproblems together .

Advantages :

1. Small source code.

2. Easy to code and understand.

Disadvantages:

1.Take a lot of memory if the recursion depth is high.

For Example, if fact( 500 ) is called,it has to push 499 intermediate results into the System’s Stack before it can evaluate the result.

Simple Optimisation:

unsigned int  fact( int n ) {

int result = 1 ;

for( int i = 2 ;  i <= n ; ++ i )

result *= i;

return result;

}

You can see that there is no time wasted in the flow of controll between functions and its sub-functions , and storing the intermediate values into the stack. You can thus save the Storing and Fetching time into the stack.

Hmm .. Its 3 : 17 A.M already , Guess i ll link you guys to more resources …

2. Fibonacci Series :

http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html

3.Towers of Hanoi:

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html

You also get the solve the Tower Of Hanoi by urself in the above link

(Browser should JavaScript 1.2 Enabled)

4.Eight Queens Problem:

http://www.animatedrecursion.com/advanced/the_eight_queens_problem.html

More general n-Queens problem :

http://theory.cs.uvic.ca/amof/e_queeI.htm

5. An example TopCoder Problem :

Problem Statement
	There is nothing more beautiful than just an integer number. You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly ktimes: Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1. Return the maximal possible number you can get at the end of this procedure. If it’s not possible to perform k operations, return -1 instead.
Constraints
-	n will be between 1 and 1,000,000, inclusive.
-	k will be between 1 and 10, inclusive.
Examples
0)
	16375 1 Returns: 76315 The optimal way is to swap 1 and 7.
1)
	432 1 Returns: 423 In this case the result is less than the given number.

More Links:

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/

http://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=Recursion&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=

- Vidya Sagar S

TopCoder Profile : http://www.topcoder.com/tc?module=MemberProfile&cr=22652618

s4sagar@gmail.com

Advertisement