# 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**?

**Example1: 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.

**Example2: 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.

**Example3: 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 Output0 0 1 1 2 return ( fib(2-1) + fib(2-2)) return ( fib(1) + fib(0)) return ( 1 + 0) = 1therefore, fib(2) = 13 return ( fib(3-1) + fib(3-2)) return ( fib(2) + fib(1)) return(1 + 1) = 2therefore, fib(3) = 24 return ( fib(4-1) + fib(4-2)) return( fib(3) + fib(2)) return(2 + 1) = 3and so on...till i = 9.

### Advantages of using recursion

**Recursion**is more elegant and requires a lesser number of variables which makes the program short and clean.**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

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions