Detailed Tutorial abut the Recurssion in C /C++

[thannara123]

Hi everybody ,
I am now going a deep study in C/C++
i haven't get a detailed idea about the recursion
Recursion is technique is calling function by it self
can you comment to get an idea about it

waiting for your valuable teaching comments
Thanking you

 

[ckshivaram]

see this
**broken link removed**
https://courses.cs.vt.edu/~cs2505/fall2009/wmcquain/Notes/pdf/T26.RecursionInC.pdf

 

[horace1]

As you say a recursive function calls itself either directly (from within itself) or indirectly (from a function which it has called). Probably the simplest example is factorial

N! = N * (N -1) * (N - 2) * (N - 3) ..... 1 N > 0

this may be evaluated using a simple for() loop or using the recursive relationship:

N! = N * (N - 1)! for N > 1
N! = 1 for N = 0 or 1

in C

/* Factorial of an integer number:  n! = n * (n -1)! down to 1!  = 1          */
long int factorial(long int n)                                                  
{                                                                               
     if (n <= 1)  return 1;                                      /* return 1! */
     return (n * factorial(n - 1));                              /* return n! */
}

In this case a simple loop is much more efficent as recursion has the overhead of function call, creation of local variables, saving paramters and local variables on the stack, etc.
However, there are algorithms in which recursion can be used effectivly, e.g. quicksort
QUICKSORT (Java, C++) | Algorithms and Data Structures

 

[thannara123]

hi Experts ,
i am not getting what is happening there
how the function will exit ?
this the my doubt
Sir also i am not well in English
because can u give explain simply
with example

thanking you

 

[horace1]

recursive functions must have some terminating condition or they will run forever (or until you run out of stack space and get a segmentation error)
consider the following version of a recursive factorial

/* Factorial of an integer number:  n! = n * (n -1)! down to 1!  = 1          */
long int factorial(long int n)
{
     int result;
     printf("called factorial(%ld)\n", n);
     if (n <= 1)  result = 1;                           /* return 1! */
     else         result = (n * factorial(n - 1));      /* return n! */
     printf("factorial(%ld) = %ld\n", n, result);
     return result;
}

int main()
{
  printf(" answer%ld\n", factorial(5));
}

when run it gives

called factorial(5)
called factorial(4)
called factorial(3)
called factorial(2)
called factorial(1)
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120
 answer120

factorial() is called to evaluate 5! it calles itself to evaluate 4! then 3! then 2! then 1!
1! = 1 which is returned as the function result, 2! is evaluated, then 3!, then 4! then 5! which is the answer