Recursion

Recursion 

A recursive function is a function that calls itself either directly or indirectly through another function. Recursion can be used directly or indirectly. 

The direct recursion function, calls itself till the condition is true. In indirect recursion, a function calls another function then the called function calls the calling function. 

We have to use recursion very carefully; otherwise it may lead to an infinite loop. In recursion, an exit condition (or a base case) is a must. 

The scope of computation should be reducing across successive recursive calls.

Factorial of a number using Recursion 

The factorial of a non-negative integer 'n' is, written as n! (And pronounced "n factorial") and is calculated by:  

n * (n-1) * (n-2) *...... *1

with 1! equal to 1, and 0! defined to be 1. 

For example, 5! is calculated as 5 *4* 3* 2 * 1, which is equal to 120. 

The factorial of an integer, greater than or equal to '0' can be calculated iteratively (non-recursively) using a "for" statement as follows: 

factorial = 1 

for (counter = number; counter >= 1; counter-- ) 

factorial *= counter;

A recursive definition of the factorial function is arrived at by observing the following relationship:

n! = n * (n-1)!

For example, 5! is clearly equal to 5 * 4! as shown by the following: 

5! = 5 * 4 * 3 * 2 * 1

5! = 5 * (4 * 3 * 2 * 1) = 5 * 4!

The evaluation of 5! will proceed as shown on the screen

// Program for recursive factorial function 

#include<stdio.h>

long factorial (long number); // function prototype 

// function main begins program execution 

int main (void) 

{

int i; // counter 

/* loop 11 times; during each iteration, calculate factorial (i) and display result */ 

for (i=0; i<=10; i++) 

{ 

print(“%2d!=%d\n”,i, factorial (i) ); 

} // end for 

return 0; // indicates successful termination 

} // end main 

// recursive definition of function factorial 

long factorial (long number) 

{

// base case 

if (number <=1)

 { 

return 1; 

} // end if

else 

{ // recursive step 

return (number * factorial (number - 1) ) ;

} // end else 

} // end function factorial 

Output:

0! =1

1! =1

2!= 2 

3!= 6 

4!= 24 

5! = 120 

6!= 720 

7! = 5040 

8!= 40320 

9!= 362880 

10!= 3628800