Recursion is a technique where a complex problem is broken down into smaller, more manageable instances of the original problem.
A recursive function is a function that calls itself to solve a complex problem by breaking it down into smaller, more manageable subproblems.
Each recursive call moves towards a base case, which is a condition that stops the recursion and returns a result directly.
Recursion is a widely used in programming for tasks such as traversing data structures, performing mathematical computations, and implementing algorithms like factorial calculation and the Fibonacci sequence.
However, it's crucial to ensure that each recursive call progresses towards the base case to prevent infinite recursion and potential stack overflows.
A recursive function in C typically consists of two main parts:
Calculating the factorial of a number is a classic example of recursion in C. The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n. For example, the factorial of 10 is as follows:
\[ 10! = 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 3,\!628,\!800 \]
#include <stdio.h>
// Recursive function to calculate factorial
long factorial(int n) {
if (n == 0) { // Base case
return 1;
} else { // Recursive case
return n * factorial(n - 1);
}
}
int main() {
int number = 5;
printf("The factorial of %d is %ld\n", number, factorial(number));
return 0;
}Output:
The factorial of 5 is 120
The Fibonacci sequence is another popular example where recursion can be used. Each number in the sequence is the sum of the two preceding ones, typically starting with 0 and 1.
#include <stdio.h>
// Recursive function to calculate nth Fibonacci number
long fibonacci(int n) {
if (n == 0) { // Base case
return 0;
} else if (n == 1) { // Base case
return 1;
} else { // Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int n = 10;
printf("The Fibonacci number at position %d is %ld\n", n, fibonacci(n));
return 0;
}Output:
The Fibonacci number at position 10 is 55
Tail recursion is a specific type of recursion where the recursive call is the last operation in the function. Some compilers can optimize tail-recursive functions to prevent additional stack frames, making them as efficient as their iterative counterparts.
#include <stdio.h>
// Tail-recursive function to calculate factorial
long factorial_tail(int n, long accumulator) {
if (n == 0) {
return accumulator;
} else {
return factorial_tail(n - 1, n * accumulator);
}
}
long factorial(int n) {
return factorial_tail(n, 1);
}
int main() {
int number = 5;
printf("The factorial of %d is %ld\n", number, factorial(number));
return 0;
}Output:
The factorial of 5 is 120Palindrome checker: write a recursive function to check if a given string is a palindrome.
LogicA palindrome is a word, phrase, number, or other sequence of characters that reads the same forward or backward (ignoring spaces, punctuation, and capitalization). Here are some examples of palindrome words:
When you read the above words backwards, they remain the same.
To check if a string is a palindrome using recursion, follow these steps:
Example program in C to check if a string is a palindrome using recursion technique.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
// Function to preprocess the string: remove non-alphanumeric and convert to lowercase
void preprocess(char *str, char *processed) {
int j = 0;
for(int i = 0; str[i] != '\0'; i++) {
if(isalnum(str[i])) {
processed[j++] = tolower(str[i]);
}
}
processed[j] = '\0';
}
// Recursive function to check palindrome
int is_palindrome(char *str, int start, int end) {
if(start >= end) {
return 1; // Base case: all characters matched
}
if(str[start] != str[end]) {
return 0; // Mismatch found
}
return is_palindrome(str, start + 1, end - 1); // Recursive call
}
int main() {
char input[100];
char processed[100];
printf("Enter a string: ");
fflush(stdout);
fgets(input, sizeof(input), stdin);
input[strcspn(input, "\n")] = 0; // Remove trailing newline
preprocess(input, processed);
int len = strlen(processed);
if(is_palindrome(processed, 0, len - 1)) {
printf("\"%s\" is a palindrome.\n", input);
} else {
printf("\"%s\" is not a palindrome.\n", input);
}
return 0;
}Sample output:
Enter a string: A man, a plan, a canal: Panama
"A man, a plan, a canal: Panama" is a palindrome. Logic
Binary search is an efficient algorithm for finding the position of an item from a sorted list of items. It works by repeatedly dividing the search interval in half.
Example program in C implementing the binary search algorithm using recursion
#include <stdio.h>
// Recursive binary search function
int binary_search(int arr[], int low, int high, int target) {
if(high >= low) {
int mid = low + (high - low) / 2;
// If the element is present at the middle
if(arr[mid] == target)
return mid;
// If element is smaller than mid, it can only be present in left subarray
if(arr[mid] > target)
return binary_search(arr, low, mid - 1, target);
// Else the element can only be present in right subarray
return binary_search(arr, mid + 1, high, target);
}
// Element is not present in the array
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/sizeof(arr[0]);
int target = 10;
int result = binary_search(arr, 0, n - 1, target);
if(result != -1)
printf("Element is present at index %d.\n", result);
else
printf("Element is not present in the array.\n");
return 0;
}Sample output:
Element is present at index 3.Tower of Hanoi: solve the Tower of Hanoi problem recursively.
Logic
The Tower of Hanoi is a classic problem involving three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest at the top, making a conical shape.
The objective is to move the entire stack to another rod, following these simple rules:
Below is a visualization of the Tower of Hanoi. You start with the following placement.
You need to end up with the following stack after moving each disk following the described rules previously.
Now that you understand what a Tower of Hanoi is, let's use a recursion in C to solve our problem.
Recursive solution:
n disks from the source rod to the destination rod using an auxiliary rod:
n-1 disks from the source rod to the auxiliary rod.n-1 disks from the auxiliary rod to the destination rod.Program in C
#include <stdio.h>
// Recursive function to solve Tower of Hanoi
void tower_of_hanoi(int n, char source, char destination, char auxiliary) {
if(n == 1) {
printf("Move disk 1 from rod %c to rod %c.\n", source, destination);
return;
}
// Move top n-1 disks from source to auxiliary
tower_of_hanoi(n - 1, source, auxiliary, destination);
// Move the nth disk from source to destination
printf("Move disk %d from rod %c to rod %c.\n", n, source, destination);
// Move the n-1 disks from auxiliary to destination
tower_of_hanoi(n - 1, auxiliary, destination, source);
}
int main() {
int n = 3; // Number of disks
printf("The sequence of moves involved in the Tower of Hanoi are:\n");
tower_of_hanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}Sample output:
The sequence of moves involved in the Tower of Hanoi are:
Move disk 1 from rod A to rod C.
Move disk 2 from rod A to rod B.
Move disk 1 from rod C to rod B.
Move disk 3 from rod A to rod C.
Move disk 1 from rod B to rod A.
Move disk 2 from rod B to rod C.
Move disk 1 from rod A to rod C.
Recursion is a fundamental concept in programming that, when used appropriately, can simplify complex problems and lead to more readable and maintainable code. However, it's essential to be mindful of its drawbacks, such as potential performance issues and the risk of stack overflow. Understanding when and how to use recursion effectively is key to leveraging its full potential in C programming.
