Recursion in C Programming

In this article, we are going to learn about the recursion in C programming language, what is recursion, types of recursion and recursion program in C?
Submitted by Sudarshan Paul, on June 12, 2018

The recursion is a technique of programming in C and various other high-level languages in which a particular function calls itself either in a direct or indirect manner. The use of recursive algorithm can make certain complex programming problems to be solved with ease.

How to go about solving problems involving recursion?

Recursion algorithms can sometimes turn out to be difficult to understand for beginners and intermediate programmers. However, a particular approach to recursive problems can simplify the process by a great margin.

1) You must apply your ideas with a recursive approach to the problems involving recursion.

2) Keep in mind most of the recursive problems have two cases:

2.1) Base Case:
The base case is the simplified form of the problem, which has no further scope of expression into its own terms i.e. the function is no more called and the recursion terminates. Because of this, it is also referred to as the termination condition. The base case can be omitted if you desire to form an infinite recursion.

int fact(int n)
{
	if (n <= 1) // base case
		return 1;
	else    
		return n*fact(n-1);   
}

For example, in the above code snippet (n<=1) is the base case for the function fact.

2.2) Recursive Case:
In recursive case, there is further scope for the problem to be defined in terms of itself, which in turn reduces the problem size.

3) Now that you know what Base and Recursive cases are, next step is expressing your problem in the form of these two cases.

fact(n) = {1}
{n*fact(n-1)}

4) Now that you have the two cases with you, last step is to simply code for the recurrence relation.

Direct and Indirect Recursion Techniques

Direct recursion is simply the function calling itself i.e. the function body contains an explicit call to itself. On the other hand, Indirect recursion occurs when a function body calls a different function which in turn calls another function, ultimately resulting in the original function being called in the process. The functions involved in indirect recursion are called mutually recursive functions. Comparatively, it is simpler and safer to use direct recursion as it is much easier to understand and apply.

Example to solve recursion problems,

The below program gives an illustration of finding the factorial of a number using recursion in C.

#include <stdio.h>

unsigned long long int factorial(unsigned int i) 
{
	if(i<= 1) 
	{
		return 1;
	}
	return i * factorial(i - 1);
}

int  main() 
{
	int i = 12;
	
	printf("Factorial of %d is %ld\n", i, factorial(i));
	
	return 0;
}

Output

    Factorial of 12 is 479001600

Recursive Programming Vs Iterative Programming

Recursive programming as discussed earlier involves recursive function whereas in Iterative programming we use loops ( some commonly used loops are ‘for’, ‘while’, do-while loops).

Now, let's look at the difference between the two.

Recursive Programming	Iterative Programming
Recursive program has greater space requirements.	Iterative programming consumes less space
It has greater time requirements for operation because of function calls and return overhead.	They operate faster than recursive functions.
Recursive functions can be solved iteratively.	Iterative functions can be solved recursively.
Inherently recursive program include Tower of Hanoi problem.	Simple iterative program include finding sum of first n numbers.