Home » C programming language

Recursion Tutorial, Example, Advantages and Disadvantages in C language

In this article, we will learn all about recursion, its usage, advantages and disadvantages in C programming language.
Submitted by Sneha Dujaniya, on August 13, 2018

Prerequisite: Recursion in C language

Recursive function

A function which calls itself is a recursive function. There is basically a statement somewhere inside the function which calls itself. It is also sometimes called a "circular definition".

Let us see, how recursion works through examples?

Print the sum of 10 natural numbers using recursion

#include <stdio.h>

//function declaration
int sum(int);

//main code

int main()
{
	int n, add;

	printf("Enter the number of natural numbers to be added: ");
	scanf("%d",&n);

	add = sum(n);

	printf("The sum of the first %d natural numbers is %d",n,add);
	
	return 0;
}

//recursion function definition
int sum(int n)
{
	if (n == 0)
		return 0;
	else
		return(n + sum(n-1));  //calling function itself
}

Output

    Enter the number of natural numbers to be added: 10
    The sum of the first 10 natural numbers is 55

Dry run of the program:

When we enter the value of n = 10, the sum function is called with n as 10. Now, since n is not equal to 0, what gets returned is (n + sum(n-1)), i.e., (10+sum(9)). As you can see, the function gets called again inside the function itself.

Now, next output is (10 + 9 + sum(8)).

Then, (10 + 9 + 8 + sum(7)) and so on till (10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)).

Here, when the function is called with n = 0, the return value is 0. This actually looks like (10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0) which equals to 55.

Calculating factorial of a number using recursion

#include <stdio.h>

//function declaration
int fact (int);

//main code
int main ()
{
	int n, result;

	printf ("Enter a number whose factorial is to be calculated: ");
	scanf ("%d", &n);
	
	if (n < 0)
	{
		printf ("Fatorial does not exist.");
	}
	else
	{
		result = fact(n);
		printf("Factorial of %d is %d.", n,result);
	}

	return 0;
}

//recursion function definition
int fact (int n)
{
	if (n == 0 || n == 1)
		return 1;
	else
		return (n * fact (n - 1)); //calling function definition
}

Output

    Enter a number whose factorial is to be calculated: 5
    Factorial of 5 is 120.

Dry run of the program

As it is clear from the program, if we enter a value less than 0, the factorial does not exist and the program ends after that. If we enter 0 or 1, factorial will be 1. Else, what gets returned is (n*fact(n-1)), i.e., (5*fact(4)). As you can see, the function gets called again inside the function itself just like the program above.

Next output is (5*4*fact(3)) and so on till (5*4*3*2*fact(1)). Here, what gets returned is 1. So, it looks like (5*4*3*2*1) which is equal to 120.

Print Fibonacci series using recursion

Fibonacci series is a series of integers in which every number is the sum of two preceding numbers. The first two numbers are 0 and 1 and then the third number is the sum of 0 and 1 that is 1, the fourth number is the sum of second and third, i.e., 1 and 1 and equal 2. It can be written in the simplest form as fn = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

#include <stdio.h>

//function declaration
int fib(int);

//Main code
int main()	
{
	int n, i;
	
	printf("Enter the number of values to be printed from the fibonacci series: ");
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
		printf("%d ",fib(i));

	return 0;
}

//recursion function definition
int fib(int a)
{
	if (a==0)
		return 0;
	if (a==1)
		return 1;
	else
		return(fib(a-1) + fib(a-2)); //calling function itself
}

Output

    Enter the number of values to be printed from the fibonacci series: 10
    0 1 1 2 3 5 8 13 21 34 

Dry run of the program

    i	Output

    0	0

    1	1

    2	return ( fib(2-1) + fib(2-2))
        return ( fib(1) + fib(0))
        return ( 1 + 0) = 1   therefore, fib(2) = 1

    3	return ( fib(3-1) + fib(3-2))
        return ( fib(2) + fib(1))
        return(1 + 1) = 2   therefore, fib(3) = 2

    4	return ( fib(4-1) + fib(4-2))
        return( fib(3) + fib(2))
        return(2 + 1) = 3 and so on... till i = 9.

Advantages of using recursion

1. Recursion is more elegant and requires a lesser number of variables which makes the program short and clean.
2. Recursion can be made to replace complex nesting codes since we don’t have to call the program, again and again, to do the same task as it calls itself.

Disadvantages of using recursion

1. It is comparatively difficult to think of the logic of a recursive function.
2. It also sometimes becomes difficult to debug a recursive code.