grimes13

 Profile Answers by grimes13 

• Mar 8th, 2010

 

Recursion is where one function calls itself

void foo()
{
  foo();
}

recursion is used to create data structures and used to traverse data structures

Be carefull because you might recurse infinitly like the example function I wrote.

kbjarnason

 Profile Answers by kbjarnason 

• Jul 2nd, 2010

 

Recursion occurs when a function, either directly or indirectly, calls itself.  An example might be a factorial function:

unsigned fact(unsigned n)
{
   /* 0! is by definition 1; */
   if ( n == 0 || n == 1 )
     return 1;

   return n * fact(n-1);
}


Pass it the value 3:

   3 is neither 0 nor 1, so call fact(2)
      2 is neither 0 nor 1, so call fact(1)
         1 is 1, so return 1
      return 2 * result, which was 1, so 2
   return 3 * result, which was 2, so 6

Voila; 3! is 6.  To achieve this, fact used recursion, calling itself repeatedly until a boundary condition (n == 0 or n == 1) was met.  As the recursion unwinds, the results at each level are returned, multiplied by the parent level's value, returned and so on, until the recursion is completely unwound and the result is returned to the caller.

A slightly more useful situation for recursion is in sorting, such as quicksort.  The idea is that each level "divides" the data to be sorted into two parts, then sorts each part - by calling itself again, just using first the one "divided" portion of the data, then the next.

It should be apparent that if you divide any data set enough times, you'll eventually wind up with no more than two values, at which point it is trivial to compare them and swap if necessary.

Recursion need not be direct.  Function A may call B, which may call C, which may in turn call A again, thus resulting in recursion, but the idea is the same - A ends up being called repeatedly, from within either A or something A has called, thus looping back on itself, just "one level deeper".

Jitendra Chittoda

• Sep 4th, 2011

 

Stack data structure is used to maintain the information about the recursive functions.