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
