Day 5: Recursion Implementation in Binary Search and Linear Search Algorithms

Title: Understanding Recursion in Linear and Binary Search Algorithms

Recursion is a powerful concept in computer science and programming. It involves a function calling itself, making it a useful tool for solving complex problems by breaking them down into smaller, more manageable parts. In the world of Data Structures and Algorithms (DSA), recursion finds practical application in various searching algorithms like linear search and binary search.

Linear Search Using Recursion

Linear search is a simple searching algorithm where we go through each element of an array to find a particular value. Implementing linear search using recursion involves breaking down the search process into smaller parts until the desired value is found or the entire array is traversed.

Here's a basic implementation of linear search using recursion in C++:

#include <iostream>
using namespace std;

bool linearSearch(int arr[], int size, int key) {
    // Base case: if the size of the array becomes 0, return false
    if (size == 0) {
        return false;
    }
    // Check if the first element is the key
    if (arr[0] == key) {
        return true;
    } else {
        // Recursively call the function with a reduced array size
        return linearSearch(arr + 1, size - 1, key);
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    bool ans = linearSearch(arr, 5, 7);
    if (ans) {
        cout << "Present" << endl;
    } else {
        cout << "Absent" << endl;
    }

    return 0;
}

In this example, if the key is not found within the array, the output will be "Absent."

Binary Search Using Recursion

Binary search is a more efficient search algorithm that works on sorted arrays by continually dividing the search interval in half. This process efficiently narrows down the search space.

Here's a basic implementation of binary search using recursion in C++:

#include <iostream>
using namespace std;

bool BinarySearch(int arr[], int start, int end, int size, int key) {
    // Base case: if the starting point is greater than the ending point, return false
    if (start > end) {
        return false;
    }
    int mid = start + (end - start) / 2;

    if (arr[mid] == key) {
        return true;
    } else if (arr[mid] < key) {
        return BinarySearch(arr, mid + 1, end, size, key);
    } else {
        return BinarySearch(arr, start, mid - 1, size, key);
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    bool ans = BinarySearch(arr, 0, 4, 5, 5);
    if (ans) {
        cout << "Present" << endl;
    } else {
        cout << "Absent" << endl;
    }

    return 0;
}

In this example, since the key is present in the array, the output will be "Present."

Both linear search and binary search, when implemented using recursion, demonstrate how a problem can be broken down into simpler parts, enabling efficient searching in arrays. While linear search sequentially checks each element, binary search's division and conquering strategy offer faster results, especially in sorted arrays. Understanding and utilizing recursion in these algorithms provide insight into their working principles and application in practical programming scenarios.