Learn C Programming Language

# 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