Recursion

What is recursion? Which data structure is used for recursion

Questions by Dheerendra_juli

Showing Answers 1 - 9 of 9 Answers

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.

  Was this answer useful?  Yes

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".

  Was this answer useful?  Yes

Jitendra Chittoda

  • Sep 4th, 2011
 

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

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions