When to use recursion ?

Hi,

According to my book it says that interation (loops), in many cases, can be use instead of recursion. But in some cases, recursion mimics the problem better. My question is simply when is a good time to use recursion and if possible provide an example.

note: I am more comfortable when using loops....


many thnx

Recursion is best used when a recursive solution makes the code simpler and easier to follow.

Iteration is best used when a recursive solution doesn't make the program much simpler or when a recursive solution is devastatingly inefficient.

A good example of recursion is a binary search for a binary tree.
It's efficient enough for the purposes and vastly improves the readability of the program.

A terrible example of recursion is the fibonacci program.
It follows the mathomatical algorithm better than the iterative solution, but it doesn't make the code much easier to follow or shorter and it's so inefficient you don't want to imagine.

A lot of mathematical functions are recursive relations. The Fibonacci numbers, the Mandelbrot-set, the factorial function etc.

It is often very easy to implement these relations as recursive functions in a programming language.

A very much used example, the factorial function:

n! = n x (n - 1) x (n - 2) x ... x 2 x 1

int fac (int n)
{
if (n == 1)
return 1;
else
return (n * fac (n - 1));
}

But there are many more applications of recursion.

Recursion is mainly used in algorithm design phase, where you concentrate on designing an algorithm to solve certain problem and you don't want to worry about optimizations. When the algorithm design has finished, you can optimize it and also take the language you will be using in account.

In almost all cases, if not all cases, recursion can be removed. There are many techniques for removing recursion. They were developed since not all languages do support recursion.

There are some costs associated with using recursion. The recursive function is copied onto the stack each time it calls itself. This takes time and memory not required in solutions using iteration.

The previous posters hit the mark when they advised you to only use recursion when it makes the code easier to follow. Most likely, you will use recursion when forced to by your instructor or university professor. :)

My experience has been that recursion is mostly used in searching and sorting problems where a divide-and-conquer method is used. Divide-and-conquer refers to solving a problem with a large data set by reducing it to two smaller data sets, and solving for each of those.

Sometimes recusrion just makes more sense. For example, the towers of Hanoi (http://www.cut-the-knot.com/recurrence/hanoi.html)....

Code:

---

void hanoi (int src, int aux, int dest, int num)
{
 if (num != 0)
 {
  // Move the pegs above to the auxillary peg...
  hanoi (src, dest, aux, num - 1);
 
  // Move the current peg to the destination peg...
  printf ("Peg moved from %d to %d.\n", src, dest);

  // Move the pegs from the auxillary peg to dest
  hanoi (aux, src, dest, num - 1);
 }
 return;
}

---

Other problems too, like say, try to find how many paths there are from the bottom left cell of a square to the top right cell of the square. These are problems where a stack needs to be used, and it's often more convenient to use the function's stack than try to make your own.

If you're interested, you might want to check out a book on fractals. Those pretty much are recursive by definition.

thnx

other than maths functions which i'm not good at and algorithms, is there a live example which can also be solved by recursion?

thnx for all replies so far.

I have an idea. When almost in every iteration you have more

if (To do like you have done && have value of variables will be needed again)
go for recursion call;

It is more important for thinking style for successfull implementation of divide and conquer type of problem.

Best way is to see some problem which were solved recursive way.

thnx

Did you see the other thread called 'Towers of Hanoi' ?
If anyone knows the recursive solution OR iterative solution to the problem pls post it, i don't know how to solve that even with pseudocode code.

thnx a lot