Types of Searching Algorithms
When it comes to searching algorithms, there are two main categories: linear search and binary search.
1. Linear Search
- Also known as sequential search
- Starts at the beginning of the array and compares each element with the target element sequentially
- Suitable for unsorted or small arrays
- Time complexity: O(n), where n is the size of the array
- Can be implemented using loops or recursion
2. Binary Search
- Requires a sorted array
- Starts at the middle of the array & compares the middle element with the target element
- If the target is less than the middle element, the search continues in the left half of the array.
- If the target is greater than the middle element, the search continues in the right half of the array
- Repeated until the target is found or the search space is exhausted
- Time complexity: O(log n), where n is the size of the array
- More efficient than linear search for large sorted arrays
How Linear Search Works?
Linear search works by sequentially comparing each element of the array with the target element until a match is found or the end of the array is reached. Let’s look at how the recursive approach to linear search works:
1. The recursive function takes the array, the size of the array, and the target element as parameters.
2. The base case for the recursion is when the array size becomes 0. If the size is 0 and the target element is not found, the function returns -1 to indicate that the element is not present in the array.
3. If the size is not 0, the function compares the first element of the array with the target element. If they match, the function returns the index of the current element.
4. If the first element does not match the target, the function recursively calls itself with the array starting from the second element (index 1), the size reduced by 1, and the same target element.
5. The recursive calls continue until either the target element is found or the base case is reached.
6. If the target element is found, the function returns the index of the element. If the element is not found, the function returns -1.
Let’s look at a step-by-step example of how recursive linear search works:
Let's say we have an array [5, 2, 9, 1, 7], and we want to search for the target element 9.
1. The initial call to the recursive function passes the array, size as 5, and target as 9.
2. The function compares 5 with 9. They don't match, so it recursively calls itself with the array starting from index 1 ([2, 9, 1, 7]), size as 4, and target as 9.
3. The function compares 2 with 9. They don't match, so it recursively calls itself with the array starting from index 2 ([9, 1, 7]), size as 3, and target as 9.
4. The function compares 9 with 9. Since they match, the function returns the current index, which is 2.
The recursive calls stack up until the target element is found or the base case is reached.
Pseudocode for Recursive Linear Search
The pseudocode for the recursive linear search algorithm is:
function recursiveLinearSearch(array, size, target):
if size == 0:
return -1
if array[0] == target:
return 0
else:
result = recursiveLinearSearch(array[1:], size - 1, target)
if result == -1:
return -1
else:
return result + 1
In this pseudocode:
1. The function takes in the array, its size, & the target element as parameters.
2. It starts with the base case: if the size is 0, meaning the array is empty, it returns -1 to indicate that the target element is not found.
3. If the size is not 0, it compares the first element of the array (array[0]) with the target element.
4. If they match, it returns 0, indicating that the target element is found at index 0.
5. If they don't match, the function recursively calls itself with the array starting from the second element (array[1:]), size reduced by 1, & the same target element.
6. The recursive call returns the result, which is either -1 if the target is not found, or the index of the target element relative to the subarray.
7. If the result is -1, meaning the target was not found in the subarray, the function returns -1.
8. If the result is not -1, the function returns the result incremented by 1 to account for the index shift in the original array.
The recursive calls continue until either the target element is found or the base case is reached.
Implementation of Recursive Linear Search:
Let’s see the implementation of recursive linear search in C:
#include <stdio.h>
int recursiveLinearSearch(int arr[], int size, int target) {
// Base case: if size becomes 0, target not found
if (size == 0) {
return -1;
}
// If first element matches the target, return its index
if (arr[0] == target) {
return 0;
}
// Recursive call with array starting from the second element
int result = recursiveLinearSearch(arr + 1, size - 1, target);
// If target not found in the subarray, return -1
if (result == -1) {
return -1;
}
// If target found in the subarray, return its index + 1
return result + 1;
}
int main() {
int arr[] = {5, 2, 9, 1, 7};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 9;
int index = recursiveLinearSearch(arr, size, target);
if (index != -1) {
printf("Element %d found at index %d\n", target, index);
} else {
printf("Element %d not found in the array\n", target);
}
return 0;
}
You can also try this code with Online C Compiler
Output
Element 9 found at index 2
In this code:
1. The `recursiveLinearSearch` function takes the array, size, & target element as parameters.
2. The base case checks if the size becomes 0, indicating that the array is empty. If so, it returns -1 to signal that the target element is not found.
3. If the size is not 0, it compares the first element of the array (`arr[0]`) with the target element. If they match, it returns 0, indicating that the target element is found at index 0.
4. If the first element doesn't match, the function makes a recursive call with the array starting from the second element (`arr + 1`), size reduced by 1, & the same target element.
5. The recursive call returns the result, which is either -1 if the target is not found in the subarray, or the index of the target element relative to the subarray.
6. If the result is -1, the function returns -1 to indicate that the target element is not found.
7. If the result is not -1, the function returns the result incremented by 1 to account for the index shift in the original array.
8. In the `main` function, an example array `{5, 2, 9, 1, 7}` is created, & the target element is set to 9.
9. The `recursiveLinearSearch` function is called with the array, size, & target element.
10. The returned index is checked. If it's not -1, it means the target element is found, & its index is printed. Otherwise, a message indicating that the element is not found is printed.
The recursive linear search function keeps calling itself with smaller subarrays until the base case is reached or the target element is found.
Time & Space Complexity
Let's analyze the time & space complexity of the recursive linear search algorithm.
Time Complexity
- In the worst case, the target element is not present in the array, & the recursive function is called for each element until the size becomes 0.
- The number of recursive calls is equal to the size of the array, so the time complexity is O(n), where n is the size of the array.
- This means that the time taken by the algorithm increases linearly with the size of the array.
- In the best case, where the target element is found at the first index, the time complexity is O(1) as only one comparison is made.
- On average, the time complexity is still O(n) because the target element can be present anywhere in the array.
Space Complexity
- The space complexity refers to the amount of extra space used by the algorithm, not including the space used by the input array.
- In recursive linear search, the space complexity is determined by the number of recursive calls on the call stack.
- Each recursive call adds a new frame to the call stack, which includes the function parameters and local variables.
- In the worst case, the recursive calls go up to the base case, which means the maximum depth of the call stack is equal to the size of the array.
- Therefore, the space complexity of recursive linear search is O(n), where n is the size of the array.
This is because, in the worst case, the call stack can grow to the size of the array.
Note: While the recursive approach to linear search provides a neat and concise implementation, it has the issue of recursive function calls and increased space complexity compared to the iterative approach using loops.
Frequently Asked Questions
Can recursive linear search be used on sorted arrays?
Yes, recursive linear search can be used on sorted arrays, but it doesn't take advantage of the sorted property. Binary search is more efficient for sorted arrays.
Is recursive linear search more efficient than iterative linear search?
No, recursive linear search is generally less efficient than iterative linear search due to the overhead of recursive function calls & increased space complexity.
When is recursive linear search preferred over iterative linear search?
Recursive linear search is preferred when the problem size is small, or when demonstrating the concept of recursion. For larger arrays or performance-critical applications, iterative linear search is usually better.
Conclusion
In this article, we discussed linear search using recursion in C. We learned what linear search is and how it works with recursion, and we provided pseudocode and C code examples. We also analyzed its time and space complexity and compared it with the iterative approach. Recursive linear search offers a concise implementation but comes with the issue of recursive calls. It is suitable for small arrays or educational purposes, while iterative linear search is preferred for larger arrays and performance-critical scenarios.
You can also check out our other blogs on Code360.
19+ registered 
