Recursion

From Algorithmist
Jump to: navigation, search

Introduction

Recursion is:[edit]

   A way of thinking about problems.
   A method for solving problems.
   Related to mathematical induction.

A method is recursive if it can call itself; either directly:

   void f() {
    ... f() ...
  }

or indirectly:

 void f() {
 ... g() ...
 }
 void g() {
 ... f() ...
 }


You might wonder about the following issues:[edit]

Q: Does using recursion usually make your code faster?

A: No.

Q: Does using recursion usually use less memory?

A: No.

Q: Then why use recursion?

A: It sometimes makes your code much simpler!


One way to think about recursion:[edit]

When a recursive call is made, the method clones itself, making new copies of the code the local variables (with their initial values), the parameters.

Each copy of the code includes a marker indicating the current position. When a recursive call is made, the marker in the old copy of the code is just after the call; the marker in the "cloned" copy is at the beginning of the method.

When the method returns, that clone goes away, but the previous ones are still there, and know what to execute next because their current position in the code was saved (indicated by the marker).


Here's an example of a simple recursive method:[edit]

void printInt( int k ) {
  if (k == 0) {
  return;
  }
  System.out.println( k );
  printInt( k - 1 );
  System.out.println("all done");
}


Rules of recursion[edit]

                                                *** RECURSION RULE #1 ***

Every recursive method must have a base case -- a condition under which no recursive call is made -- to prevent infinite recursion. Here's another example; this version does have a base case, but the call badPrint2(2) will still cause an infinite recursion:

 void badPrint2( int k ) {
   if (k < 0) return;
   System.out.println(k);
   badPrint2( k+1 );
 }


                                                *** RECURSION RULE #2 ***

Every recursive method must make progress toward the base case to prevent infinite recursion.


Recursion vs Iteration[edit]

Now let's think about when it is a good idea to use recursion and why. In many cases there will be a choice: many methods can be written either with or without using recursion.

Q: Is the recursive version usually faster?

A: No -- it's usually slower (due to the overhead of maintaining the stack)

Q: Does the recursive version usually use less memory?

A: No -- it usually uses more memory (for the stack).

Q: Then why use recursion??

A: Sometimes it is much simpler to write the recursive version.

Q: Why recursion is slower:

A: self check using the example of factorial.(Hint: It does lots of recomputation.)

Q: Is there any other method to solve recursive solvable problems?

A: Yes, they can be solved by iteratively using Dynamic Programming, Divide and conquer and many more methods.


Summary[edit]

Use recursion for clarity, and (sometimes) for a reduction in the time needed to write and debug code, not for space savings or speed of execution.

Remember that every recursive method must have a base case (rule #1).

Also remember that every recursive method must make progress towards its base case (rule #2).

Sometimes a recursive method has more to do following a recursive call. It gets done only after the recursive call (and all calls it makes) finishes.

Recursion is often simple and elegant, can be efficient, and tends to be underutilized. Consider using recursion when solving a problem!