# 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. |

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