C Program Linear Search Using Recursive Function

In this article, you will learn how to implement a linear search algorithm using a recursive function in C. This method provides an alternative perspective to the traditional iterative approach, leveraging the power of recursion to traverse data structures.

Problem Statement

The core problem of a linear search is to find the position of a target element within an unsorted list or array. Given an array of elements and a specific value, the task is to determine if the value exists in the array and, if so, return its index. If the value is not found, a specific indicator (like -1) should be returned. This is a fundamental search problem often encountered when data is not sorted, making more efficient search algorithms like binary search inapplicable.

Example

Imagine you have a small list of numbers: [10, 25, 8, 42, 17]. If you search for the number 8, the linear search would return its index: 2. If you search for the number 99, the linear search would indicate that it's not found, perhaps by returning -1.

Background & Knowledge Prerequisites

To understand a recursive linear search, readers should be familiar with the following concepts:

• C Language Basics: Variables, arrays, function definitions, conditional statements (if-else).
• Functions: How to declare, define, and call functions, including passing parameters.
• Recursion: The concept of a function calling itself, including understanding base cases and recursive steps.
• Arrays: How arrays are indexed and how to access elements.

Use Cases or Case Studies

Linear search, especially in its recursive form, is useful in several scenarios:

• Small Datasets: When the number of elements is very small, the overhead of more complex algorithms isn't justified, and linear search provides a simple solution.
• Unsorted Data: It's the go-to algorithm for finding an element in data that isn't sorted, as it doesn't require any pre-processing.
• Simple Inventory Systems: Searching for a specific item by name or ID in a small, unindexed list of products.
• Configuration Files: Locating a particular key-value pair in a simply structured configuration file.
• Educational Contexts: As a foundational algorithm for teaching basic search concepts and the principles of recursion.

Solution Approaches

For this problem, we will focus on one primary solution: using a recursive function.

Recursive Linear Search

This approach utilizes the principle of recursion where the function calls itself to check each subsequent element in the array until the target is found or the end of the array is reached.

One-line summary: The function checks the current element and, if not found, recursively calls itself to search the remainder of the array, stopping when the element is found or the array is exhausted.

Code Example:

// 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;
}

Run

Sample Output:

Element 89 found at index 3.
Element 100 not found in the array.

Stepwise Explanation:

1. Function Signature: recursiveLinearSearch(int arr[], int size, int target, int index) takes the array, its total size, the element to find, and the current starting index for the search.
2. Base Case 1 (Not Found): The first condition if (index == size) checks if the index has exceeded the array bounds. If true, it means we've checked every element without finding the target, so -1 is returned. This is crucial to prevent infinite recursion.
3. Base Case 2 (Found): The second condition if (arr[index] == target) checks if the element at the current index matches the target. If true, the target is found, and its index is returned. This is another stopping condition for the recursion.
4. Recursive Step: If neither base case is met, the function return recursiveLinearSearch(arr, size, target, index + 1); calls itself. This time, it passes index + 1, effectively moving to the next element in the array for the subsequent search.
5. Initial Call: In main(), the search is initiated by calling recursiveLinearSearch(arr, size, target, 0), starting the search from the beginning of the array (index 0).

Conclusion

Implementing a linear search using recursion offers an elegant way to solve the problem of finding an element in an unsorted array. While the recursive approach for linear search might have a slightly higher overhead due to function call stack management compared to an iterative version, it beautifully demonstrates the principles of recursion, including base cases and recursive steps. This method is valuable for understanding recursive problem-solving, particularly in educational contexts or for small datasets where simplicity is prioritized.

Summary

• Problem: Locate a target element within an unsorted array.
• Approach: Utilizes a recursive function that calls itself.
• Base Cases:
• Target found: Return its index.
• Array exhausted: Return -1 (not found).
• Recursive Step: If not found at the current index, search the rest of the array by incrementing the index in the recursive call.
• Use Cases: Small datasets, unsorted arrays, educational demonstrations.