What is recursion?

A function that calls itself is known as recursive function and this technique is known as recursion in C programming.

Example of recursion in C programming

Write a C program to find sum of first n natural numbers using recursion. Note: Positive integers are known as natural number i.e. 1, 2, 3....n

#include <stdio.h>

#include<conio.h>

int sum(int n);

void  main(){

    int num,add;

    clrscr();

    printf("Enter a positive integer:\n");

    scanf("%d",&num);

    add=sum(num);

    printf("sum=%d",add);

    getch();

}

int sum(int n){

    if(n==0)

       return n;

    else

       return n+sum(n-1);    /*self call  to function sum() */

}

Output

Enter a positive integer:

5

15

In, this simple C program, sum() function is invoked from the same function. If n is not equal to 0 then, the function calls itself passing argument 1 less than the previous argument it was 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 value of n is returned which is the sum numbers from 5 to 1.

For better visualization of recursion in this example:

sum(5)

=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

Every recursive function must be provided with a way to end the recursion. In this example when, n is equal to 0, there is no recursive call and recursion ends.

Advantages and Disadvantages of Recursion

Recursion is more elegant and requires few variables which make program clean. Recursion can be used to replace complex nesting code by dividing the problem into same problem of its sub-type.

In other hand, it is hard to think the logic of a recursive function. It is also difficult to debug the code containing recursion.