Recursion in C Language is a powerful concept where a function calls itself directly or indirectly to solve a problem.
It allows a function to divide a problem into smaller subproblems and solve each subproblem independently.
Here's a example of a recursive function in C:
#include <stdio.h>
int factorial(int n) {
// Base case: factorial of 0 is 1
if (n == 0)
return 1;
// Recursive case: factorial of n is n multiplied by factorial of n-1
else
return n * factorial(n - 1);
}
int main() {
int num = 5;
printf("Factorial of %d is %d\n", num, factorial(num));
return 0;
}
the "factorial()" function calls itself with a smaller argument until it reaches the base case where "n" becomes "0".
Then it starts returning values, and those values are multiplied to give the final factorial value.
When working with recursive functions, it's important to have a base case that stops the recursion and prevents infinite looping.
Also, recursive functions can be less efficient in terms of memory and performance compared to iterative solutions, particularly for large inputs, due to the overhead of function calls and maintaining function call stack.
Factorial of 5 is 120
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 10;
printf("Fibonacci series up to %d terms:\n", n);
for (int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
printf("\n");
return 0;
}
Generating Fibonacci series using recursion.
Step 1: Loop start with `i` which is `0` initially, and pass to the `Fibonacci` function. it verifies condition `0` <= `1` and returns 0.
Step 2: Now `i` value is `1`, and pass to the `Fibonacci` function. it verifies condition `1` <= `1` and returns 1.
Step 3: Now `i` value is `2`, and pass to the `Fibonacci` function. it does not verify condition `2` <= `1` and move to the else condition fibonacci(2 - 1) + fibonacci(2 - 2) which equals to `fibonacci(1) + fibonacci(0)` and fibonacci(1) return us `1` and fibonacci(0) return `0`. so 1 + 0 = 1.
Step 4: Now `i` value is `3`, and pass to the `Fibonacci` function. it does not verify condition `3` <= `1` and move to the else condition fibonacci(3 - 1) + fibonacci(3 - 2) which equals to `fibonacci(2) + fibonacci(1)` and fibonacci(2) return us `1` and fibonacci(1) return `1`. so 1 + 1 = 2.
Step 5: Now `i` value is `4`, and pass to the `Fibonacci` function. it does not verify condition `4` <= `1` and move to the else condition fibonacci(4 - 1) + fibonacci(4 - 2) which equals to `fibonacci(3) + fibonacci(2)` and fibonacci(3) return us `2` and fibonacci(2) return `1`. so 2 + 1 = 3.
similarly, it will iterate up to index `9`.
Fibonacci series up to 10 terms: 0 1 1 2 3 5 8 13 21 34
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
if (low > high)
return -1; // key not found
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
return binarySearch(arr, mid + 1, high, key);
else
return binarySearch(arr, low, mid - 1, key);
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 11;
int index = binarySearch(arr, 0, n - 1, key);
if (index != -1)
printf("Element found at index: %d\n", index);
else
printf("Element not found\n");
int searchNewKey = 17;
int searchNewIndex = binarySearch(arr, 0, n - 1, searchNewKey);
if (searchNewIndex != -1)
printf("Element found at index: %d\n", searchNewIndex);
else
printf("Element not found\n");
return 0;
}
Implementing binary search using recursion.
Step 1: we pass the "key" whose value is "11" to be searched from an array. binarySearch function parameters will be `binarySearch(arr, 0, 10 -1, 11).
Step 2: It will check condition `low > high` whose original values are: `0 > 9` condition fails, it will move further.
Step 3: It will find the `mid` value, using low and high so it will mid = (0 + 9)/2 = 4. so mid = 4
Step 4: It will check condition `arr[mid] == key` whose original values are: `arr[4] == 11` and on array index 4 we have value 9, so the condition becomes `9 == 11` and condition fails it moves further and check for `else if` condition `( 9 < 11)` and condition found truthy and code enter inside `else-if` condition.
Step 5: in the `else-if` condition we have the `binarySearch(arr, mid + 1, high, key)` function whose parameters are `binarySearch(arr, 4 + 1, 9, 11)`. now `binarySearch` function is called recursively with new parameters but the same above steps we need to validate.
Step 6: It will check condition `low > high` whose original values are: `5 > 9` condition fails, it will move further.
Step 7: It will find the `mid` value, using low and high so it will mid = (5 + 9)/2 = 7. So now mid = 7.
Step 8: It will check condition `arr[mid] == key` whose original values are: `arr[7] == 11` and on array index 7 we have value 15, so the condition becomes `15 == 11` and condition fails it moves further and check for `else if` condition `( 15 < 11)` and condition found falsely and code move inside `else` condition.
Step 9: in the `else` condition we have the `binarySearch(arr, low, mid - 1, key)` function whose parameters are `binarySearch(arr, 5, 7-1, 11)`. now `binarySearch` function is called recursively with new parameters but the same above steps we need to validate again.
Step 10: It will check condition `low > high` whose original values are: `5 > 6` condition fails, it will move further.
Step 11: It will find the `mid` value again, using low and high so it will mid = (5 + 6)/2 = 5. so mid = 5
Step 12: It will check condition `arr[mid] == key` whose original values are: `arr[5] == 11` and on array index 5 we have value 11, so the condition becomes `11 == 11` and condition found truthy and returns mid value which is `5`
Element found at index: 5 Element found at index: 8
Recursion is a powerful tool for solving problems that can be broken down into smaller, similar subproblems.
However, it's important to be cautious about stack overflow errors and inefficiencies for large inputs.