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.
Login to rate this answer.
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".
Login to rate this answer.
Jitendra Chittoda
Answered On : Sep 4th, 2011
Stack data structure is used to maintain the information about the recursive functions.
Login to rate this answer.
