In this tutorial, we are going to learn about the **fundamentals of recursion functions**.

In **C** language it is possible for **functions** to call themselves.

## C – Fundamentals of Recursion functions:

A function is called recursive if a statement within the body of the function **calls** the same function. This is also known as a **circular definition** or **self-reference**.

There is a distinct difference between the **normal** and **recursive** functions.

- A
**normal function**will be invoked by another function. - A
**recursive function**is invoked by itself**directly**or**indirectly**as long as the given condition is satisfied.

Recursive functions are useful while constructing the **data structures** like stacks, queues, linked lists and trees.

Every **recursive function** must satisfy the following two criteria’s or properties.

**Base criteria**: There must be at least one base criteria or condition in the recursion process, such that, when this condition is met the function stops calling itself recursively.**Recursive step**: The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

A recursive function that satisfies the above two properties is said to be a **well defined recursive function**.

Recursion function calls can be classified into the below two types:

- When a function calls itself directly, it is called a direct recursion. In such cases,
**only one function is involved**, which calls itself until the given condition is met. - In indirect recursion
**two or more functions can be involved**, where the recursive call be initiated by one of the intermediary functions.

```
// Direct recursion
int sum(int n) {
.......
if (condition) {
variable = sum(n-1);
}
}
```

```
// Indirect recursion
int sum(int n) {
.......
if (condition) {
variable = total(n-1);
}
}
int total(int n) {
.......
if (condition) {
variable = sum(n-1);
}
}
```

While using recursion, programmers need to be careful **to define an exit condition from the function**, otherwise, the calls might result in an **infinite loop**.

**Recursive functions** are very useful to solve many mathematical problems like calculating factorial, generating Fibonacci series, etc.

Some of the **important points** to remember when writing a program involving recursion process.

- In recursion, it is essential for a function to
**call itself**; otherwise, recursion will not take place. - Only
**user-defined functions**can be involved in the recursion.**Library function cannot be involved in recursion**because their source code cannot be viewed. - To
**stop the recursive function**it is necessary to base the recursion on test condition and proper terminating statement. - During recursion, at each recursive call
**new memory is allocated to all the local variables**of the recursive functions with the same name. - When a recursive function is executed, all the recursive calls are pushed onto the
**stack**until the terminating condition is not detected. When the terminating condition is detected, the recursive calls stored in the stack are popped and executed. The last call is executed first then second, then third and so on.

The below sample code is to find the factorial of a given number using recursion process.

First let us consider the mathematical solution of the factorial problem.

- The factorial of a number 3 can be calculated as 3! = 3 * 2 * 1
- The factorial of a number 4 can be calculated as 4! = 4 * 3 * 2 * 1
- The factorial of a number 5 can be calculated as 5! = 5 * 4 * 3 * 2 * 1
- In the similar way factorial of a number n can be calculated as n! = n * (n – 1) * (n – 2) *….3 * 2 * 1

The recursive formula for factorial is:

n! = n * (n - 1)!; if n > 0 (Recursive criteria) n! = 1; if n = 0 (Base criteria)

In the factorial program write the main() and factorial() functions. In main() function read the input and send it to the factorial() function.

The factorial() function contains **base** and **recursive** criteria, where the base condition executes only when the value reaches zero (0).

```
#include <stdio.h>
long int factorial(long int);
void main() {
long int n;
printf("Enter an integer : ");
scanf("%ld", &n);
printf("Factorial of %ld is %ld\n", n, factorial(n));
}
long int factorial(long int n) {
if (n <= 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
```

Output:

```
Enter an integer : 5
Factorial of 5 is 120
```

## Advantages and Disadvantages of recursion:

Some of the **advantages** of using **recursion** are :

- Using recursion, code becomes more
**readable**while implementing**data structures**like stacks, queues, linked lists and trees. - Using recursion, a program can be written in a
**concise**form (shorter way).

Some of the **disadvantages** of using **recursion** are :

- It requires
**extra storage space**. The recursive calls and automatic variables are stored on the function call**stack**. For every recursive call, separate memory is allocated to automatic variables on the function call stack. - The recursive functions are not always efficient in
**execution speed**as they have to push and pop the data on the function call stack.

## REFERENCES:

Happy Learning 🙂