Recursion in C


Introduction

Recursion is a powerful and fundamental concept in computer science and programming. It allows a function to call itself, enabling the solution of complex problems through smaller, more manageable instances. In this guide, we'll explore the principles of recursion in C and provide sample code to illustrate its usage.


Key Concepts

Before we dive into examples, let's cover some key concepts related to recursion:

  • Base Case: Every recursive function should have a base case. It defines when the recursion should stop and provides a solution for the simplest, smallest instance of the problem.
  • Recursive Case: The recursive case defines how the problem is reduced or divided into smaller subproblems. It typically involves calling the function recursively with modified inputs.

Sample Code

Let's explore some examples of recursion in C:


Factorial Calculation

#include <stdio.h>
// Recursive function to calculate the factorial of a number
int factorial(int n) {
if (n <= 1) {
return 1; // Base case: factorial of 0 and 1 is 1
} else {
return n * factorial(n - 1); // Recursive case
}
}
int main() {
int n = 5;
int result = factorial(n);
printf("Factorial of %d is %d\\n", n, result);
return 0;
}

Fibonacci Sequence

#include <stdio.h>
// Recursive function to calculate the nth Fibonacci number
int fibonacci(int n) {
if (n <= 0) {
return 0; // Base case: Fibonacci(0) is 0
} else if (n == 1) {
return 1; // Base case: Fibonacci(1) is 1
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
}
int main() {
int n = 10;
int result = fibonacci(n);
printf("Fibonacci(%d) is %d\\n", n, result);
return 0;
}

Recursive Binary Search

#include <stdio.h>
// Recursive function to perform binary search
int binarySearch(int arr[], int left, int right, int target) {
if (left > right) {
return -1; // Base case: element not found
}
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid; // Base case: element found
} else if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target); // Search the left half
} else {
return binarySearch(arr, mid + 1, right, target); // Search the right half
}
}
int main() {
int arr[] = {2, 4, 7, 9, 12, 15, 18, 22, 25, 30};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 18;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1) {
printf("Element found at index %d\\n", result);
} else {
printf("Element not found.\\n");
}
return 0;
}

Conclusion

Recursion is a powerful technique that simplifies problem-solving by breaking down complex tasks into smaller, more manageable parts. This guide has introduced you to the key concepts of recursion in C, including base cases and recursive cases. Sample code illustrates its usage for calculating factorials, generating Fibonacci numbers, and performing binary searches. As you continue your C programming journey, you'll find recursion to be a valuable tool for solving a wide range of problems.