- The basic definition of a recursive function can be given as below:

A function that calls itself is known as recursive function and the process in which a function calls itself is known as recursion.

### Example of Recursion in C programming

- To understand the concept of recursion consider the following program calculating sum of first
*n*natural numbers using recursion.

**Note:**Positive integers are known as natural number i.e. 1, 2, 3….n

`/* C program to calculate sum of first `*n* natural numbrs.*/
#include "stdio.h"
int sum(int n); // function prototype
void main()
{
int num,add;
printf("Enter a positive integer:\n");
scanf("%d",&num);
add=sum(num); // function call
printf("sum=%d",add);
}
/* Recursive function definition */
int sum(int n)
{
if(n==0) /* condition to break recursion */
return n;
else
return n + sum(n-1); /* recursive call to function sum() */
}

**Output:**

```
Enter a positive integer:
5
15
```

- In, the above program,
*sum()*function is invoked from within the same function. - If
*n*is not equal to 0 then, the function calls itself passing argument 1 less than the argument it was previously called with.

- Suppose,
*n*is 5 initially. Then, during next function calls, 4 is passed to function and the value of argument decreases by 1 in each recursive call.

- When,
*n*becomes equal to 0, the condition for breaking recursion evaluates to true and hence the value of*n*is returned which is the sum numbers from 5 to 1.

- The below is the complete recursion calls for better visualization of recursion process:

```
sum(5) // initial call to sum() function
=5+sum(4)
=5+4+sum(3)
=5+4+3+sum(2)
=5+4+3+2+sum(1)
=5+4+3+2+1+sum(0)
=5+4+3+2+1+0
=5+4+3+2+1
=5+4+3+3
=5+4+6
=5+10
=15
```

- Note that there must be some way to end the recursion. In this example when,
*n*is equal to 0, there is no recursive call and recursion ends.

### Advantages

- Recursion is more powerful and requires few variables which make program clean.

- It can be used to replace complex nesting code by dividing the problem into same problem of its sub-type.

- Recursion can replace large program logic with a few line of code and thus, helps to reduce program code.

### Disadvantages

- The major difficulty with recursion is that it is hard to think the logic of a recursive function.

- It is also difficult to debug the code containing recursion.

### Comparison of Recursion and iteration

Recursion | Iteration |
---|---|

Recursion is the term given to the mechanism of defining a set or procedure in terms of itself. | Iteration is the block of statement executed repeatedly using loops. |

A conditional statement is required in the body of the function for stopping the function execution |
The iteration control statement itself contains statement for stopping the iteration. At every execution, the condition is checked. |

At some places, use of recursion generates extra overhead. so its better to skip when easy solution is available with iteration. | All problems can be solved with iteration. |

Recursion is expensive in terms of speed and memory. |
Iteration does not create any overhead. All the programming languages support iteration. |

- While using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go in infinite loop.

- Recursive function are very useful to solve many mathematical problems like calculating factorial of a number, generating Fibonacci series, etc