Recursion

[Sidro]

Howdy all,

Can someone summarize the important concepts of recursion for me? Like first of all its definition,how to implement it, and maybe an example of how it works.
thanks in advance!

 

[BoulderBum]

Recursion is simply code that calls itself. It consists of processing code, and a termination condition that will mark the end of the calls. (If the termination condition is never reached or there is no termination condition, the code will be stuck in an infinate loop)

For example, 5 factorial (5!), is:
5 * 4 * 3 * 2 * 1

You can get 5! by multiplying 5 * 4!. i.e. 4! is 4 * 3 * 2 * 1, so 5 * 4! is:
5 * ( 4 * 3 * 2 * 1 )

Further, you can get 4! by multiplying 4 * 3!, etc.


To handle this problem recursively, define what needs to be found for the result of N!, in this case N * ( N-1 )!, and define the termination condition, in this case N <= 1.

Now you can have a recursive function to calculate factorials:

int factorial( const int N )
{
if ( N > 1 ) //if termination condition not true
return N * factorial( N - 1 );//call self recursively
else
return N;
}

Let's say you pass 5 to factorial. Here's what it finds:

5 * 4! where 4! is
4 * 3! where 3! is
3 * 2! where 2! is
2

so 2 is returned, and calculation is made for 3 * 2!
3 * 2 so 6 is returned and the next calculation is made
4 * 6 so 24 is returned
5 * 24 = 96

So factorial( 5 ) returns 96.

Recursion simplifies many complex algorithms, but the cost for simplicity is added overhead.

Tell me if I can explain further.

 

[xwb]

A simple short definition

recursion: see recursion