Recursion in C programming



Definition of recursive function

A recursive function is a function that calls itself either directly or indirectly through another function. Recursion is a complex topic discussed at length in upper-level computer science courses.

A recursive function is called to solve a problem. The function actually knows how to solve only the simplest case(s), or so-called base case(s).

If the function is called with a base case, the function simply returns a result. If the function is called with a more complex problem, the function divides the problem into two conceptual pieces: a piece that the function knows how to do and a piece that it does not know how to do.

To make recursion feasible, the latter piece must resemble the original problem, but be a slightly simpler or smaller version.

Because this new problem looks like the original problem, the function launches (calls) a fresh copy of itself to go to work on the smaller problem—this is referred to as a recursive call or the recursion step.

The recursion step also includes the keyword return, because its result will be combined with the portion of the problem the function knew how to solve to form a result that will be passed back to the original caller.

Recursively Calculating Factorials:

In Math the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n.

The code below show the factorial in c programming:

   
    // Recursive factorial function..
    #include <stdio.h>
    unsigned long long int factorial( unsigned int number );
    
    // function main begins program execution 
    int main( void )  {
    unsigned int i,n; // counter 
    printf("Please insert the number : ");
	scanf ("%d" ,&n);
        // during each iteration, calculate 
    
    // factorial( i ) and display result 
    for ( i = 0; i <= n; ++i ) {
    printf( "%u! = %llu\n", i, factorial( i ) );
    } // end for 
    } // end main 
    
    // recursive definition of function factorial   
    unsigned long long int factorial( unsigned int number ) {                                                      
    
    // base case                                         
    if ( number <= 1 ) {                                
      return 1;                                        
    } // end if                                          
    else { // recursive step                             
      return ( number * factorial( number - 1 ) );     
    } // end else                                        
   } // end function factorial    

    Output:
    Please insert the number : 10
    0! = 1
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120
    6! = 720
    7! = 5040
    8! = 40320
    9! = 362880
    10! = 3628800

Fibonacci Series


    0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The Fibonacci series begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.

   
    // Recursive fibonacci function
    #include <stdio.h> 
    
    // function prototype 
    unsigned long long int fibonacci( unsigned int n );
    
    // function main begins program execution 
    int main( void ) {
    unsigned long long int result; // fibonacci value 
    unsigned int number; // number input by user
    
    // obtain integer from user 
    printf( "%s", "Enter an integer: " );
    scanf( "%u", &number );
    
    // calculate fibonacci value for number input by user 
    result = fibonacci( number );
    
    // display result 
    printf( "Fibonacci( %u ) = %llu\n", number, result );
    } // end main 
    
    // Recursive definition of function fibonacci               
    unsigned long long int fibonacci( unsigned int n )      
    {                                                         
    
    // base case                                            
    if ( 0 == n || 1 == n ) {                               
      return n;                                            
    } // end if                                            
    else { // recursive step                             
      return fibonacci( n - 1 ) + fibonacci( n - 2 );        
     } // end else                                         
  } // end function fibonacci     

    Output:
    Enter an integer : 10
    Fibonacci<10> = 55

Ads Right