Recursion in C

In this tutorial, you will learn about recursion in C. A recursive function calls itself to solve a problem. It is useful for tasks like factorials and Fibonacci numbers. Every recursive function needs a stopping point to avoid infinite loops. Let’s see how it works!

Contents:

1. What is Recursion in C?
2. How Recursion Works in C
3. Base Case and Recursive Case in C
4. Fibonacci Series Using Recursion in C
5. Sum of Natural Numbers Using Recursion in C
6. Reverse a String Using Recursion in C
7. Types of Recursion in C
8. Tail Recursion vs. Non-Tail Recursion in C
9. Advantages of Recursion in C
10. Disadvantages of Recursion in C
11. FAQs on Recursion in C

What is Recursion in C?

Recursion in C is a programming technique where a function calls itself to solve smaller instances of a problem. It continues calling itself until it reaches a base condition, which stops the recursion.

Syntax:

returnType functionName(parameters) {
    if (base_condition)  
        return some_value;  
    else  
        return functionName(modified_parameters);  // Recursive call  
}

How Recursion Works in C

Recursion in C works when a function calls itself with modified parameters until it reaches a stopping condition (base case). Each function call goes onto the call stack, and once the base case is met, the program resolves the calls in reverse order.

Steps in Recursion Execution:

• Function Calls Itself: The function repeats with updated arguments.
• Base Case Check: The program checks a condition to stop further recursive calls.
• Call Stack Management: The system stores each call in the stack until reaching the base case.
• Stack Unwinding: After reaching the base case, the program resolves calls in reverse order.

Example: Factorial Calculation using Recursion

#include <stdio.h>
 
// Recursive function to find factorial
int factorial(int n) {
    if (n == 0)  
        return 1;  // Base condition
    return n * factorial(n - 1);  // Recursive call
}
 
int main() {
    int num;
 
    printf("Enter a number: ");
    scanf("%d", &num);
 
    printf("Factorial of %d is %d\n", num, factorial(num));
 
    return 0;
}

Output:

Enter a number: 5
Factorial of 5 is 120

Step-by-Step Execution (for n = 5):

1. factorial(5) = 5 * factorial(4)
2. factorial(4) = 4 * factorial(3)
3. factorial(3) = 3 * factorial(2)
4. factorial(2) = 2 * factorial(1)
5. factorial(1) = 1 * factorial(0)
6. factorial(0) = 1 (Base condition met, recursion stops)
7. Now, values are returned in reverse order:
• factorial(1) = 1 * 1 = 1
• factorial(2) = 2 * 1 = 2
• factorial(3) = 3 * 2 = 6
• factorial(4) = 4 * 6 = 24
• factorial(5) = 5 * 24 = 120

Base Case and Recursive Case in C

Recursion in C consists of two main parts:

• Base Case: The condition that stops the recursion.
• Recursive Case: The function calls itself with a modified argument to progress toward the base case.

1. Base Case

The base case is the stopping condition that prevents infinite recursion. Without it, the function would call itself endlessly and cause a stack overflow.

Example: Base Case in Factorial Function

int factorial(int n) {
    if (n == 0)  // Base Case: Stops recursion
        return 1;
    else
        return n * factorial(n - 1);  // Recursive Case
}

Here, if (n == 0) return 1; is the base case because the factorial of 0 is 1, and no further recursive calls are needed.

2. Recursive Case

The recursive case is where the function calls itself to break the problem into smaller parts until the base case is reached.

Example: Recursive Case in Factorial Function

return n * factorial(n - 1);

This reduces n! to n * (n-1)! until it reaches factorial(0).

Fibonacci Series Using Recursion in C

The Fibonacci series is a sequence where each number is the sum of the two preceding ones, starting from 0 and 1.

Formula: F(n)=F(n−1)+F(n−2)
with base cases: F(0)=0,F(1)=1

C Program to Print Fibonacci Series Using Recursion

#include <stdio.h>
 
// Recursive function to return Fibonacci number
int fibonacci(int n) {
    if (n == 0) // Base Case 1
        return 0;
    else if (n == 1) // Base Case 2
        return 1;
    return fibonacci(n - 1) + fibonacci(n - 2); // Recursive Case
}
 
int main() {
    int n = 10; // Number of terms
    printf("Fibonacci Series up to %d terms:\n", n);
 
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
 
    return 0;
}

Output:

Fibonacci Series up to 10 terms:
0 1 1 2 3 5 8 13 21 34

This C program calculates Fibonacci numbers using recursion. The fibonacci() function calls itself to compute each term based on the sum of the two previous terms. The base cases handle n = 0 and n = 1. The program prints the Fibonacci series up to n terms using a loop.

Sum of Natural Numbers Using Recursion in C

The sum of the first n natural numbers can be calculated using recursion.

Formula: S(n)=n+S(n−1)
with the base case: S(0)=0

C Program to Find Sum of Natural Numbers Using Recursion

#include <stdio.h>
 
// Recursive function to calculate sum of natural numbers
int sum(int n) {
    if (n == 0) // Base Case
        return 0;
    return n + sum(n - 1); // Recursive Case
}
 
int main() {
    int n = 10; // Change this value to find sum of different numbers
    printf("Sum of first %d natural numbers: %d\n", n, sum(n));
    return 0;
}

Output:

Sum of first 10 natural numbers: 55

This C program calculates the sum of the first n natural numbers using recursion. The sum() function calls itself with n – 1 until it reaches the base case (n = 0). The main function sets n = 10 and prints the sum using printf().

Reverse a String Using Recursion in C

Recursion can be used to reverse a string by swapping characters from both ends until the middle of the string is reached.

C Program to Reverse a String Using Recursion

#include <stdio.h>
#include <string.h>
 
// Recursive function to reverse a string
void reverseString(char str[], int start, int end) {
    if (start >= end) // Base Case
        return;
 
    // Swap characters
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;
 
    // Recursive call
    reverseString(str, start + 1, end - 1);
}
 
int main() {
    char str[] = "Sanfoundry";
    int length = strlen(str);
 
    reverseString(str, 0, length - 1); // Call recursive function
 
    printf("Reversed String: %s\n", str);
    return 0;
}

Output:

Reversed String: yrdnuofnaS

This C program reverses a string using recursion. The reverseString() function swaps characters from the start and end until they meet in the middle. It calls itself with updated indices. The main function initializes “Sanfoundry”, gets its length using strlen(), and calls reverseString(). Finally, the reversed string is printed using printf().

Types of Recursion in C

Recursion in C can be categorized into different types based on how the recursive function calls itself.

1. Direct Recursion
In direct recursion, a function calls itself directly within its body.

Example: Factorial Calculation

#include <stdio.h>
 
int factorial(int n) {
    if (n == 0) // Base case
        return 1;
    return n * factorial(n - 1); // Recursive call
}
 
int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Output:

Factorial of 5: 120

2. Indirect Recursion

In indirect recursion, two or more functions call each other in a cycle.

Example: Even and Odd Check

#include <stdio.h>
 
void isEven(int n);
void isOdd(int n);
 
void isEven(int n) {
    if (n == 0)
        printf("Even\n");
    else
        isOdd(n - 1); // Calling isOdd()
}
 
void isOdd(int n) {
    if (n == 0)
        printf("Odd\n");
    else
        isEven(n - 1); // Calling isEven()
}
 
int main() {
    isEven(5);
    return 0;
}

Output:

Odd

3. Tail Recursion

In tail recursion, the recursive call is the last operation performed by the function. It helps in compiler optimizations.

Example: Tail Recursive Factorial

#include <stdio.h>
 
int factorial(int n, int result) {
    if (n == 0)
        return result;
    return factorial(n - 1, n * result);
}
 
int main() {
    printf("Factorial of 5: %d\n", factorial(5, 1));
    return 0;
}

Output:

Factorial of 5: 120

4. Non-Tail Recursion

In non-tail recursion, the recursive call is not the last operation in the function.

Example: Fibonacci Series

#include <stdio.h>
 
int sumOfDigits(int n) {
    if (n == 0) 
        return 0;
    return (n % 10) + sumOfDigits(n / 10); // Recursive call is not last
}
 
int main() {
    int num = 1234;
    printf("Sum of digits of %d is: %d\n", num, sumOfDigits(num));
    return 0;
}

Output:
Sum of digits of 1234 is: 10

5. Nested Recursion

In nested recursion, a function’s recursive call passes another recursive call as its argument.

Example: Nested Function Call

#include <stdio.h>
 
int nestedRecursion(int n) {
    if (n > 100)
        return n - 10;
    return nestedRecursion(nestedRecursion(n + 11));
}
 
int main() {
    printf("Result: %d\n", nestedRecursion(95));
    return 0;
}

Output:

Result: 91

Tail Recursion vs. Non-Tail Recursion in C

Here’s a comparison table between Tail Recursion and Non-Tail Recursion in C:

Advantages of Recursion in C

• Simplifies Complex Problems – Recursion makes solving complex problems easier by breaking them into smaller, manageable parts.
• Reduces Code Length – Recursive solutions often need fewer lines of code, especially for tasks like tree traversal.
• Fits Certain Problems Naturally – Recursion works well for divide and conquer methods, backtracking, and hierarchical data structures.
• Manages Stack Automatically – The function call stack is handled by the system, making recursion useful for depth-first search and expression evaluation.

Disadvantages of Recursion in C

• Uses More Memory – Each recursive call adds a new entry to the stack, which increases memory usage.
• Risk of Stack Overflow – Too many recursive calls can exceed the stack limit and crash the program.
• Slower Execution – Function calls take extra time, making recursion less efficient than loops in many cases.
• Harder to Debug – Following the flow of recursive calls can be confusing, making debugging more difficult.

FAQs on Recursion in C

1. What is recursion in C?
Recursion is a process where a function calls itself to solve smaller instances of a problem until a base condition is met.

2. How does recursion work in C?
A recursive function repeatedly calls itself, reducing the problem size with each call. It stops when it reaches a base case, preventing infinite recursion.

3. What are the key components of recursion?
Recursion consists of two parts:

• Base Case – The condition that stops recursion.
• Recursive Case – The part where the function calls itself with a smaller input.

4. When should recursion be used?
Recursion is useful for solving problems that involve divide and conquer, tree and graph traversal, backtracking, and problems with a recursive structure, like Fibonacci series and factorial calculation.

5. What are the disadvantages of recursion?
Recursion can lead to high memory usage, stack overflow, and increased execution time due to function call overhead.

6. How to prevent stack overflow in recursion?
Limit recursion depth, use tail recursion where possible, and consider iterative solutions for problems with large inputs.

7. Can every recursive function be converted into an iterative function?
Yes, recursion can always be replaced with iteration using loops and an explicit stack in some cases.

8. What are some common examples of recursion in C?
Common examples of recursion in C include factorial, Fibonacci series, sum of natural numbers, string reversal, Tower of Hanoi, binary tree traversal, Merge Sort, and Quick Sort.