**Recursion in C**.

Recursive Functions in C |

## Overview:

- What is Recursion?
- Types of Recursion
- Conditions of Recursive functions
- Problem-solving using Recursion
- Stack Overflow in Recursive functions
- Memory Allocation in Recursive functions
- Recursive program vs Iterative program

## What is Recursion?

**Recursion**is a process where a

**function calls itself repeatedly**either directly or indirectly. Such functions that carry out the process of recursion are called

**recursive functions**. C supports recursion, i.e., a

**self-calling function**. However, programmers must pay attention to prescribe an

**exit condition from the function**, else the program will execute itself to eternity.

Recursive functions are very useful in solving mathematical problems, like finding the factorial of a number, generating a Fibonacci series, and a lot more.

## Types of Recursion

Based on the**path of calling function**, recursion can be classified into different types. Before moving into the

**types of recursion**, let us understand the following example:

If a function f1() calls itself from its own body, it is called

**recursive**. Again, if a function f1() calls another function f2() that again redirects to f1() in the end, then that too can be considered a

**recursive function**.

So let's point down types of recursions:

### Linear Recursion:

When a function is invoked in**linear recursion**, the self-calling is made exactly

**once**. Such recursion allows the size of function to grow in a linear proportion wrt size of the program.

```
#include<stdio.h>
#define SIZE 10
int recursiveMax(int *,int);
int max(int,int);
int main()
{
int arr[SIZE]={1,3,5,4,7,19,6,11,10,2};
int max=recursiveMax(arr,SIZE);
printf("Maximum element among array items is: %d\n", max);
}
int recursiveMax(int *arr,int n)
{
if (n==1)
return arr[0];
return max(recursiveMax(arr,n-1),arr[n-1]);
}
/*function to compute max of two decimal integers*/
int max(int n,int m)
{
if (n>m)
return n;
else
return m;
}
```

#### Output:

Linear Recursion Output |

### Tail Recursion:

Just like linear recursion, but the calling is made at the**last operation**. Also, keep in mind that the

**last operation**and

**last statement**are

**not identical**. If you see at recursiveMax (defined above), then you will find that recursive call to function recursiveMax is the last statement but not last operation, code arr[n-1] yet to be processed to complete the execution of the last statement.

Thus, a

**tail-recursive**function is one where the function call is the

**last thing**the function performs. Any function that uses tail recursion can be converted to non-recursive one, by iterating through the recursive calls instead of

**calling them explicitly**. Reversing array elements is a good example of tail recursion.

```
#include<stdio.h>
#define SIZE 5
void recursiveRev(int *,int,int);
int main ()
{
int arr[SIZE]={1,2,3,4,5};
int i;
recursiveRev(arr,0,SIZE-1);
printf ("Printing array elements after they are reversed...\n");
for(i=0;i<SIZE;i++)
printf("%d\n",arr[i]);
}
void recursiveRev(int *arr,int i,int j)
{
if(i<j)
{
int tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
recursiveRev(arr,i+1,j-1);
}
}
```

#### Output:

Tail Recursion Output |

### Binary Recursion:

Binary means two units. A function that makes**two recursive calls**to itself when invoked is a

**Binary Recursion**function. Fibonacci series is a great example to show binary recursion.

```
#include<stdio.h>
int recursiveFib(int);
int main ()
{
int n=10;
printf("%dth fibonacci number is %d\n",n,recursiveFib(n));
}
int recursiveFib(int n)
{
/*base case*/
if(n<=1)
return n;
/*binary recursive call*/
return recursiveFib(n-1)+recursiveFib(n-2);
}
```

#### Output:

Binary Recursion Output |

### Multiple Recursion:

A generalised form of binary recursion. When a function makes**multiple recursive**calls (more than two) then it is called

**multiple recursion**.

## Conditions of Recursive functions

In recursive program, the solution to base case is provided and solution of bigger problem is expressed in terms of smaller problems.```
int fact(int n)
{
if (n<=1) /*base case*/
return 1;
else
return n*fact(n-1);
}
```

In the above example, base case for n<=1 is defined and larger value of number can be solved by converting to smaller one unless base case is met.

## Problem-solving using Recursion

The idea of recursive functions is to represent a problem in terms of one or more smaller problems, and to stop recursion one or more base conditions are added. For example, while computing factorial of n we have to know factorial of (n-1). Base case for factorial would be n=0. The function will return 1 when n=0.## Stack Overflow in Recursive functions

If base case is not reached or not defined, then stack overflow problem may arise. Take a look at following example to understand this:```
int fact(int n)
{
/*wrong base case (might cause stack overflow).*/
if (n==50)
return 1;
else
return n*fact(n-1);
}
```

If fact(20) is called, it will call fact(19), fact(18), fact(17) and so on but number will never reach 50. Thus, the base case is never met. If the memory is exhausted due to these functions on stack, it will result in

**stack overflow error**.

## Memory Allocation in Recursive functions

Whenever a recursive function is called in the main() function,**memory is allocated**to that function on a

**stack**. Every time the recursive function calls itself, memory for the function called is allocated above the function calling and each time a new set of space is allocated for the variables contained in the function body.

Once the condition (base case) is reached, the

**called function**returns its value to the

**function by whom it is called**and memory is de-allocated and the process goes on.

## Recursive program vs Iterative program

Let me tell you both recursive, as well as the iterative approach in any program, has almost**likely powers**. Since the nature of execution in both the approaches

**remains the same.**However, there is a slight difference that goes unnoticed.

In the case of

**Recursive Approach**, until the base condition is met, the

**functions are stacked**as a result of which it consumes a

**decent amount of space**in the memory. Adding to that, a large function will definitely take

**larger time of execution**on calling itself repeatedly.

If you're wondering that Recursive Approach is not profitable then I must mention, the above detail is not all. There are a

**few advantages**of Recursive Functions over Iterations as well.

Recursion needs

**lesser codes**to be written than the iterative version. Recursion codes are

**cleaner, compact and easy to comprehend**.

All programs written in this post are compiled online.

### Books I Prefer:

I hope this article was helpful to understand

**recursive functions**in C! Comment below, if you've got any question. Head back soon for another interesting article on C Programming.