Example: Recursive Linear Search in C

// Recursive Linear Search
#include <stdio.h>

// Function to perform recursive linear search
// arr[]: The array to search in
// size: The total size of the array
// target: The element to search for
// index: The current index being checked
int recursiveLinearSearch(int arr[], int size, int target, int index) {
    // Step 1: Base Case 1 - If the index reaches the size of the array,
    //         it means the entire array has been traversed and the target was not found.
    if (index == size) {
        return -1; // Element not found
    }

    // Step 2: Base Case 2 - If the element at the current index matches the target,
    //         the element is found, and its index is returned.
    if (arr[index] == target) {
        return index; // Element found at current index
    }

    // Step 3: Recursive Step - If the element is not found at the current index,
    //         call the function recursively for the rest of the array (increment index).
    return recursiveLinearSearch(arr, size, target, index + 1);
}

int main() {
    // Step 1: Define an array and its size.
    int arr[] = {12, 34, 5, 89, 7, 23, 67};
    int size = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Define the target element to search for.
    int target1 = 89;
    int target2 = 100;

    // Step 3: Perform the search for target1 and print the result.
    int result1 = recursiveLinearSearch(arr, size, target1, 0);
    if (result1 != -1) {
        printf("Element %d found at index %d.\n", target1, result1);
    } else {
        printf("Element %d not found in the array.\n", target1);
    }

    // Step 4: Perform the search for target2 and print the result.
    int result2 = recursiveLinearSearch(arr, size, target2, 0);
    if (result2 != -1) {
        printf("Element %d found at index %d.\n", target2, result2);
    } else {
        printf("Element %d not found in the array.\n", target2);
    }

    return 0;
}