Recursion

View chapters from top of the tab for more information.

Note: If you haven't study the function yet visit now . Because you are not going to understand this recursive function unless you have completed your function topic clearly.

Subscribe my youtube channel, link is given below.

click on this ⇒⇒A step Up

Recursion in C

• It is a process in which problem is defined in terms of itself.

• It solved problems by repeatedly breaking it into smaller and smaller problems. And that is similar in the nature of the original problems.

• It is a type of function which calls itself in the same function .

• To implement the recursion technique in the programming, that function should be capable of calling itself.

Syntax:-

int main(void)

{

   ….

  recursion();

   ….

 }

  void recursion()

  {

   ……

   recusrcion();

   ……

  }

➤How to write a recursive function?

Before writing a recursive function , we should able to define the solution of the problems in terms of a similar type of similar problems. Recusrion is all about a way of thinking about the problems.

The two main steps to keep in mind before writing the recursive function is that:-

1.           Identification of the base case and its solution.

     2.       Identification of the general case or the recursive case or the case in which recursive function  will be made.

It is very important to identifying the base case because without base case ,the function calls itself infinitely and will never terminated .

Flow of control in recursive function :-

main() { 1…..  2…..  3 rec(5);  4….. }

          

                             now n is 5

void rec(int n) { 1…..   2 if(n==1)   3 return;   4……..   5 rec(n-2);   6……}

 now n is 3

void rec(int n) { 1…..   2 if (n==1)   3 return;   4……..   5 rec(n-2);   6……. }

                               

          now n is 1

void rec(int n) { 1……   2 if (n==1)   3 return;   4…….   5 rec(n-2);   6…… }

1.       At initial main() function calls the rec() function , so at first instance value of formal parameter n is 5. After that rec() is called ,then it checked the terminating condition and since it is false we don’t return.  Now next line is executed and after that rec() is again called with argument 3.


2.       Now controls transfer to the second instance of rec(). value of n is 3. then it checked the terminating condition and since it is false we don’t return.  Now next line is executed and after that rec() is again called with argument 3.

     3.     Now controls transfer to the third  instance of rec(). value of n is 1. then it checked the terminating condition and since it is true ,now we return.

       4.     We now return to the second instance of the rec() at the next line. and after executing the next line we return back to the first instance.

       5.   We are now inside first instance of rec(). And after executing the next line we return to the main() at next line.

The number of times that a function calls itself is known as recursive depth of that function.

➤Winding and Unwinding phase:-

All recursive function generally work in two phases i.e, so called winding and unwinding phase.

Winding phase starts when the recursive function calls for the first time, and each recursive call continues their winding phase . In this phase the function keeps in calling itself and no returns statements are executed . And when the terminating condition is true then this phase is terminated.

After this unwinding phase is started , in this phase the recursive function call start returning in reverse order till the first instance is met and return to the main() function. In this unwinding phase the control returns through each instance of function.

Examples 1. factorial

/* Program to find the factorial of a number by recursive method */

#include<stdio.h>

long int fact(int n);

int main(void)

{

  int num;

   printf(“enter a number : “);

  scanf(“ %d “, &num );

  if( num<0 )

   printf( “ No factorial for negative numbers \n “);

  else

     printf( “ Factorial of %d is %ld \n “ , num , fact(num) );

   return 0;

  }

 long int fact(int n)

  {

   if(n==0 )

   return 1;

    return ( n * fact ( n-1 ) );

  }

 Practice your function related programs