What is Recursive Function in C Programming?

In C programming Language, when a function calls itself then the function is called the recursive function. Recursive functions are used to solve various mathematical problems and also to traverse data structures like trees and graphs.

Recursive Function

The Recursive function is a function, that repeatedly calls itself in order to solve a problem, breaking the problem down into smaller and smaller sub-problems 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 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.

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.

// 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

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.

// 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

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.

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

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, this article will help you to understand what is the recursive function in C and how to write a recursive function in C language. In addition, you will also see a few examples of the recursive function in C to understand how the recursive functions work in C language.

FAQs Related to Recursive Function

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. What are some common problems with recursive functions?
Some common problems with recursive functions include infinite recursion, stack overflow, and poor performance due to high memory usage. These problems can be avoided by carefully defining the base case, properly modifying the arguments in the recursive calls, and avoiding redundant calculations.

3. How can I optimize a recursive function in C?
You can optimize a recursive function in C by using dynamic programming, memoization, or tail recursion optimization. These techniques can reduce the number of redundant calculations and improve the performance of the function.

4. When should I use a recursive function in C programming?
You should use a recursive function in C programming when the problem can be divided into smaller subproblems with similar structures. Recursive functions are often used to solve problems that can be solved by repeating the same process multiple times with different inputs, such as finding the nth Fibonacci number or calculating the factorial of a number.

5. Can a recursive function be called from another function?
Yes, a recursive function can be called from another function, just like any other function. However, care should be taken to ensure that the base case is defined correctly and that the arguments are properly modified in each recursive call.

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.