What is Recursive Function in C Programming?

Last Updated on October 18, 2023 by Ankit Kochar

Recursive functions are a fundamental concept in computer science and programming, and they play a pivotal role in languages like C. They enable a function to call itself, creating a loop-like behavior, and are essential for solving complex problems efficiently. However, recursive functions can be intimidating for beginners and even experienced programmers at times. This article aims to demystify recursive functions in C, breaking down the concept into digestible pieces and providing clear explanations and examples. Whether you’re a novice programmer looking to understand recursion or an experienced developer seeking a refresher, this guide will help you grasp the fundamentals of recursive functions and how they work in the C programming language.

What is Recursive Function in C?

The Recursive function is a function that repeatedly calls itself in order to solve a problem, breaking the problem down into smaller and smaller subproblems until it reaches a base case, at which point the solution is built up from the solutions to the sub-problems. Let’s see how the recursive function looks in C language.

Understand Recursive Function in C

In the below example, the function rec() calls itself so the function rec() is called the recursive function.

void rec()
{
    /* function calls itself */
    rec();
}

int main()
{
    rec();
}

Examples of the Recursive Functions in C Programming:

We will see a few examples to understand the recursive function in C programming:

Example 1: Factorial of the number using the recursive function in C.

The Factorial of the number N is the multiplication of natural numbers q to N.

Factorial( N ) = 1 * 2 * 3 * ….. * N-1 * N

Let’s see how to find the factorial of the given number using the recursive function in C.

// recursive function to find factorial

#include <stdio.h>

int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

int main() {
  int n;
  printf("Enter the number: ");
  scanf("%d",&n);
  int fact = factorial(n);
  printf("\nThe factorial of %d is: %d\n", n, fact);
  return 0;
}

Output:

Enter the number: 5
The factorial of 5 is: 120

In the C program, we have created the recursive function factorial(), in which there is one base to terminate the recursive class and the base case is n==0 because factorial of 0 and 1 is 1. If it is not the base case then the function calls itself for the n-1 th term and multiplies it with n and returns the answer.

Example 2: Fibonacci Series using the recursive function in C

Fibonacci series is the series, where the Nth term is the sum of the last term ( N-1 th) and the second last term (N-2 th).

fibonacci (N) = fibonacci (N-1) + fibonacci (N-2)

Let’s see how to find the fibonacci series using the recursive function in C.

// recursive function to find fibonacci

#include <stdio.h>

int fibonacci(int n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  int n;
  printf("Enter the number: ");
  scanf("%d",&n);
  int fibo = fibonacci(n);
  printf("The %dth Fibonacci number is: %d\n", n,fibo);
  return 0;
}

Output:

Enter the number: 8
The 8th Fibonacci number is: 21

In the C program, we have created the recursive function fibonacci(), in which there is one base to terminate the recursive class and the base case is n<=1 because Fibonacci of 0 and 1 is 1. If it is not the base case then the function calls itself for the n-1 th term and adds it with the n-2 th term and returns the answer.

Example 3: GCD of the given two numbers using the recursive function in C

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both of the numbers without leaving a remainder. Let’s see how to find the GCD of the two numbers using the recursive function in C.

// recursive function to find GCD

#include <stdio.h>

int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}

int main() {
  int result = gcd(24, 32);
  printf("The GCD of 24 and 32 is: %d\n", result);
  return 0;
}

Output:

The GCD of 24 and 32 is: 8

In the C program, we have created the recursive function gcd(), in which there is one base to terminate the recursive class and the base case is b==0 we will return a. If it is not the base case then we will return gcd(b, a%b).

How to Convert the Iterative Function to the Recursive Function in C?

Now, we will take an example to find the sum of the first 10 natural numbers using an iterative function and then we will convert that function into the recursive function.

#include <stdio.h>

int find_sum(int n) {
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

int main() {
  int result = find_sum(10);
  printf("The sum of the first 10 natural numbers is: %d\n", result);
  return 0;
}

Output:

The sum of the first 10 natural numbers is: 55

In the above example, we have used a for loop to find the sum of the first 10 natural numbers.

Let’s see how we can convert this iterative function to the recursive function.

#include <stdio.h>

int find_sum(int n) {
  if (n == 1) {
    return 1;
  }
  return n + find_sum(n - 1);
}

int main() {
  int result = find_sum(10);
  printf("The sum of the first 10 natural numbers is: %d\n", result);
  return 0;
}

Output:

The sum of the first 10 natural numbers is: 55

In the above example, we have created the recursive function find_sum(), in which there is one base to terminate the recursive class and the base case is n==1. If it is not the base case then the function calls itself for the n-1 th term and adds n to it.

Conclusion
In conclusion, recursive functions in C are a fundamental concept that empowers programmers to tackle complex problems by breaking them down into simpler, more manageable subproblems. By understanding the principles of recursion, you can write efficient and elegant code that solves a wide range of problems, from mathematical calculations to traversing complex data structures. However, it's essential to exercise caution and ensure that your recursive functions have well-defined base cases and termination conditions to prevent infinite loops and stack overflow errors. With practice and experience, you can harness the power of recursion to write more efficient and elegant C code.

As you delve deeper into the world of C programming, you'll discover countless opportunities to leverage recursion in your projects, making your code more modular, readable, and maintainable. So, embrace the recursive mindset, explore its possibilities, and continue refining your programming skills.

FAQs Related to Recursive Function in C

Here are some FAQs related to Recursive Function in C.
1. What is the difference between an iterative and a recursive function?
An iterative function uses loops to solve problems, while a recursive function uses the call stack to solve problems. An iterative function is often easier to understand, but a recursive function can be more elegant and concise.

2. When should I use recursion in C?
Recursion is suitable for solving problems that can be broken down into smaller, similar subproblems. Common examples include factorial calculation, Fibonacci sequence generation, and traversing tree-like data structures. Use recursion when it simplifies the problem-solving process and enhances code readability.

3. What are the advantages of using recursive functions in C?
Recursive functions can lead to more elegant and modular code, making it easier to understand and maintain. They can also provide efficient solutions to certain problems, especially when dealing with recursive data structures like trees.

4. Are there any drawbacks to using recursion in C?
Yes, there are potential drawbacks to using recursion. Recursive functions consume additional memory due to the call stack, which can lead to stack overflow errors for deep or unoptimized recursive calls. It's crucial to ensure that your recursive function has a well-defined base case and termination conditions to prevent infinite recursion.

5. How can I optimize recursive functions in C?
To optimize recursive functions in C, you can implement techniques such as memoization (caching intermediate results) or converting the recursive function into an iterative one using loops. These strategies can help reduce memory consumption and improve performance for certain recursive algorithms.

6. Can a recursive function have multiple base cases?
Yes, a recursive function can have multiple base cases, which are conditions that define when the recursion should stop. This can be useful when solving problems that have multiple solutions or multiple ways to reach the solution. In these cases, each base case can define a different end condition for the recursion.