• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

C Recursion

← Previous Next →

In C programming, recursion is a technique in which a function calls itself to solve a problem. Recursion is a powerful tool for tasks that involve repeated or nested computations, such as calculating factorials, generating Fibonacci series, traversing data structures, and solving mathematical problems.

Recursion is an alternative to iteration (loops) and allows complex problems to be broken into simpler, more manageable sub-problems. Understanding recursion is essential for writing efficient, clean, and modular code in C.

How Recursion Works

A recursive function has two main parts:

  1. Base Case: The condition under which the function stops calling itself. This prevents infinite recursion.

  2. Recursive Case: The part of the function where it calls itself with a smaller or simpler problem.

Example:

#include <stdio.h>

int factorial(int n) {
    if(n == 0) // Base case
        return 1;
    else
        return n * factorial(n - 1); // Recursive case
}

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

  • factorial() calls itself until n reaches 0.

  • The base case n == 0 stops recursion and starts returning values back through the call stack.

Types of Recursion

  1. Direct Recursion: A function calls itself directly.
    Example: factorial() in the example above.

  2. Indirect Recursion: A function calls another function, which eventually calls the original function.

#include <stdio.h>

void functionA(int n);
void functionB(int n);

void functionA(int n) {
    if(n > 0) {
        printf("A: %d\n", n);
        functionB(n - 1);
    }
}

void functionB(int n) {
    if(n > 0) {
        printf("B: %d\n", n);
        functionA(n / 2);
    }
}

int main() {
    functionA(10);
    return 0;
}

  • Here, functionA and functionB call each other indirectly.

  • Indirect recursion is less common but useful in specific scenarios.

Key Components of Recursion

  1. Termination Condition (Base Case): Without it, recursion leads to infinite calls and eventually stack overflow.

  2. Progress Toward Base Case: Each recursive call must bring the problem closer to termination.

  3. Stack Usage: Every recursive call is stored in the call stack with its parameters and local variables. After the base case is reached, the stack unwinds, returning values step by step.

Advantages of Recursion

  • Simplifies complex problems by breaking them into smaller sub-problems.

  • Improves code readability and clarity, especially for algorithms like tree traversal.

  • Recursion is a natural choice for divide-and-conquer algorithms like QuickSort or MergeSort.

  • Can replace complex nested loops with simpler recursive logic.

Disadvantages of Recursion

  • Consumes more memory due to multiple stack frames.

  • Slower than iterative solutions for simple tasks.

  • Improper termination or missing base case can cause stack overflow.

  • Debugging recursion can be tricky for beginners.

Practical Examples

1. Fibonacci Series

#include <stdio.h>

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

int main() {
    int terms = 10;
    for(int i = 0; i < terms; i++)
        printf("%d ", fibonacci(i));
    return 0;
}

  • Each call computes the sum of the two previous numbers.

  • Recursive calls continue until reaching base cases n == 0 or n == 1.

2. Sum of Natural Numbers

#include <stdio.h>

int sum(int n) {
    if(n == 0)
        return 0;
    else
        return n + sum(n - 1);
}

int main() {
    int n = 5;
    printf("Sum of first %d natural numbers is %d\n", n, sum(n));
    return 0;
}

  • Each call reduces n by 1 until 0 is reached.

  • Returns the cumulative sum during stack unwinding.

3. Reverse a Number

#include <stdio.h>

void reverse(int n) {
    if(n == 0)
        return;
    else {
        printf("%d", n % 10);
        reverse(n / 10);
    }
}

int main() {
    int num = 12345;
    printf("Reversed: ");
    reverse(num);
    return 0;
}

  • Prints digits of the number in reverse order using recursion.

  • Base case stops recursion when the number becomes 0.

Tips for Writing Recursive Functions

  1. Always define a base case.

  2. Ensure each call moves closer to the base case.

  3. Avoid unnecessary recursive calls to optimize performance.

  4. For large inputs, consider iterative solutions to prevent stack overflow.

  5. Use recursion for problems naturally suited to it, such as tree traversal, factorial, Fibonacci, or Hanoi Tower.

Summary of the Tutorial

Recursion in C is a technique where a function calls itself to solve smaller sub-problems. It consists of a base case and a recursive case, which together prevent infinite loops and enable step-by-step problem solving. Recursion simplifies complex problems, improves code readability, and is widely used in algorithms and mathematical computations. Understanding recursion is crucial for writing efficient, structured, and elegant C programs.

Practice Questions

  1. Write a recursive function to calculate the factorial of a number.

  2. Create a recursive function to print the first n terms of the Fibonacci series.

  3. Write a recursive function to find the sum of the first n natural numbers.

  4. Develop a recursive function to reverse a number and print it.

  5. Write a recursive function to calculate the power of a number (x^y).

  6. Create a recursive function to find the greatest common divisor (GCD) of two numbers.

  7. Write a recursive function to check if a string is a palindrome.

  8. Develop a recursive function to print numbers from n to 1.

  9. Write a recursive function to calculate the sum of elements in an array.

  10. Create a recursive function to solve the Tower of Hanoi problem for n disks.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

C Programming

online coding class codepractice

Introduction to C

Basics of C

Control Flow

Arrays & Strings

User Input & Output

Pointers

Functions

File Handling

Structures, Unions & Enums

Memory Management

Error Handling & Debugging

Macros and Preprocessors

codepractice logo
Login
Go Back Top