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
