Looking For Anything Specific?

How to Implement Linear Search Using Recursion in C, C++, Python, and JavaScript

Admin July 26, 2021

Linear search is a simple searching algorithm in which a sequential search is made over all items one by one. This algorithm is often implemented using the iterative approach, but sometimes the interviewers tweak the problem and ask to implement the algorithm recursively.

In this article, you'll learn how to implement the linear search algorithm using recursion in C++, Python, JavaScript, and C.

Problem Statement

You're given an unsorted array and an element to be searched in the given array. You need to write a recursive function such that if the element is found in the given array, the index of the element is returned and if the element is not found in the array, -1 is returned.

Example 1: Let arr = [1, 2, 3, 4, 5, 6, 7] and elementToBeSearched = 4

4 is present in the array at index 3.

Thus, 3 is returned from the function and "Element 4 found at index 3" is displayed on the output.

Example 2: Let arr = [1, 1, 1, 1, 1] and elementToBeSearched = 2

2 is not present in the array.

Thus, -1 is returned from the function and "Element 2 not found" is displayed on the output.

Approach to Solve the Problem

  1. Compare the element to be searched with the element at the left-most index and the right-most index in the array.
  2. If the element is found, return the index.
  3. Else recursively search the element for the rest of the array by incrementing the left index and decrementing the right index.
  4. Call the function recursively until the right index is less than the left index.

Related: How to Find the Sum of All Elements in an Array

C++ Program to Implement the Linear Search Algorithm Using Recursion

Below is the C++ program to implement the linear search algorithm using recursion:

// C++ program to recursively search an element in an array
#include <iostream>
using namespace std;
// Function to recursively search an element in an array
int recursiveSearch(int arr[], int left, int right, int elementToBeSearched)
{
 if (right < left)
 {
 return -1;
 }
 if (arr[left] == elementToBeSearched)
 {
 return left;
 }
 if (arr[right] == elementToBeSearched)
 {
 return right;
 }
 return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched);
}
void printArrayElements(int arr[], int size)
{
 for(int i=0; i<size; i++)
 {
 cout << arr[i] << " ";
 }
 cout << endl;
}
int main()
{
 int arr1[] = {1, 2, 3, 4, 5, 6, 7};
 int size1 = sizeof(arr1)/sizeof(arr1[0]);
 cout << "Array 1:" << endl;
 printArrayElements(arr1, size1);
 int elementToBeSearched1 = 4;
 cout << "Element to be searched: " << elementToBeSearched1 << endl;
 int indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1);
 if(indexOfElement1 == -1)
 {
 cout << "Element " << elementToBeSearched1 << " not found" << endl;
 }
 else
 {
 cout << "Element " << elementToBeSearched1 << " found at index " << indexOfElement1 << endl;
 }
 int arr2[] = {2, 4, 6, 10, 12, 3, 6};
 int size2 = sizeof(arr2)/sizeof(arr2[0]);
 cout << "Array 2:" << endl;
 printArrayElements(arr2, size2);
 int elementToBeSearched2 = 4;
 cout << "Element to be searched: " << elementToBeSearched2 << endl;
 int indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2);
 if(indexOfElement2 == -1)
 {
 cout << "Element " << elementToBeSearched2 << " not found" << endl;
 }
 else
 {
 cout << "Element " << elementToBeSearched2 << " found at index " << indexOfElement2 << endl;
 }
 int arr3[] = {1, 1, 1, 1, 1};
 int size3 = sizeof(arr3)/sizeof(arr3[0]);
 cout << "Array 3:" << endl;
 printArrayElements(arr3, size3);
 int elementToBeSearched3 = 2;
 cout << "Element to be searched: " << elementToBeSearched3 << endl;
 int indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3);
 if(indexOfElement3 == -1)
 {
 cout << "Element " << elementToBeSearched3 << " not found" << endl;
 }
 else
 {
 cout << "Element " << elementToBeSearched3 << " found at index " << indexOfElement3 << endl;
 }
return 0;
}

Output:

Array 1:
1 2 3 4 5 6 7
Element to be searched: 4
Element 4 found at index 3
Array 2:
2 4 6 10 12 3 6
Element to be searched: 4
Element 4 found at index 1
Array 3:
1 1 1 1 1
Element to be searched: 2
Element 2 not found

Related: An Introduction to the Merge Sort Algorithm

Python Program to Implement the Linear Search Algorithm Using Recursion

Below is the Python program to implement the linear search algorithm using recursion:

# Python program to recursively search an element in an array
# Function to recursively search an element in an arrays
def recursiveSearch(arr, left, right, elementToBeSearched):
    if right < left:
        return -1
    if arr[left] == elementToBeSearched:
        return left
    if arr[right] == elementToBeSearched:
        return right
    return recursiveSearch(arr, left+1, right-1, elementToBeSearched)
def printListElements(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()
arr1 = [1, 2, 3, 4, 5, 6, 7]
size1 = len(arr1)
print("Array 1:")
printListElements(arr1, size1)
elementToBeSearched1 = 4
print("Element to be searched:", elementToBeSearched1)
indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1)
if indexOfElement1 == -1:
    print("Element", elementToBeSearched1, "not found")
else:
    print("Element", elementToBeSearched1, "found at index", indexOfElement1)
arr2 = [2, 4, 6, 10, 12, 3, 6]
size2 = len(arr2)
print("Array 2:")
printListElements(arr2, size2)
elementToBeSearched2 = 4
print("Element to be searched:", elementToBeSearched2)
indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2)
if indexOfElement2 == -1:
    print("Element", elementToBeSearched2, "not found")
else:
    print("Element", elementToBeSearched2, "found at index", indexOfElement2)
arr3 = [1, 1, 1, 1, 1]
size3 = len(arr3)
print("Array 3:")
printListElements(arr3, size3)
elementToBeSearched3 = 2
print("Element to be searched:", elementToBeSearched3)
indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3)
if indexOfElement3 == -1:
    print("Element", elementToBeSearched3, "not found")
else:
    print("Element", elementToBeSearched3, "found at index", indexOfElement3)

Output:

Array 1:
1 2 3 4 5 6 7
Element to be searched: 4
Element 4 found at index 3
Array 2:
2 4 6 10 12 3 6
Element to be searched: 4
Element 4 found at index 1
Array 3:
1 1 1 1 1
Element to be searched: 2
Element 2 not found

Related: How to Find the Sum of Natural Numbers Using Recursion

JavaScript Program to Implement the Linear Search Algorithm Using Recursion

Below is the JavaScript program to implement the linear search algorithm using recursion:

// JavaScript program to recursively search an element in an array
// Function to recursively search an element in an array
function recursiveSearch(arr, left, right, elementToBeSearched) {
 if (right < left) {
 return -1;
 }
 if (arr[left] == elementToBeSearched) {
 return left;
 }
 if (arr[right] == elementToBeSearched) {
 return right;
 }
 return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched);
}
function printArrayElements(arr, size) {
 for(let i=0; i<size; i++) {
 document.write(arr[i] + " ");
 }
 document.write("<br>");
}
var arr1 = [1, 2, 3, 4, 5, 6, 7];
var size1 = arr1.length;
document.write("Array 1:" + "<br>");
printArrayElements(arr1, size1);
var elementToBeSearched1 = 4;
document.write("Element to be searched: " + elementToBeSearched1 + "<br>");
var indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1);
if(indexOfElement1 == -1) {
 document.write("Element " + elementToBeSearched1 + " not found" + "<br>");
} else {
 document.write("Element " + elementToBeSearched1 + " found at index " + indexOfElement1 + "<br>");
}
var arr2 = [2, 4, 6, 10, 12, 3, 6];
var size2 = arr2.length;
document.write("Array 2:" + "<br>");
printArrayElements(arr2, size2);
var elementToBeSearched2 = 4;
document.write("Element to be searched: " + elementToBeSearched2 + "<br>");
var indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2);
if(indexOfElement2 == -1) {
 document.write("Element " + elementToBeSearched2 + " not found" + "<br>");
} else {
 document.write("Element " + elementToBeSearched2 + " found at index " + indexOfElement2 + "<br>");
}
var arr3 = [1, 1, 1, 1, 1];
var size3 = arr3.length;
document.write("Array 3:" + "<br>");
printArrayElements(arr3, size3);
var elementToBeSearched3 = 2;
document.write("Element to be searched: " + elementToBeSearched3 + "<br>");
var indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3);
if(indexOfElement3 == -1) {
 document.write("Element " + elementToBeSearched3 + " not found" + "<br>");
} else {
 document.write("Element " + elementToBeSearched3 + " found at index " + indexOfElement3 + "<br>");
}

Output:

Array 1:
1 2 3 4 5 6 7
Element to be searched: 4
Element 4 found at index 3
Array 2:
2 4 6 10 12 3 6
Element to be searched: 4
Element 4 found at index 1
Array 3:
1 1 1 1 1
Element to be searched: 2
Element 2 not found

Related: An Introduction to the Bubble Sort Algorithm

C Program to Implement the Linear Search Algorithm Using Recursion

Below is the C program to implement the linear search algorithm using recursion:

// C program to recursively search an element in an array
#include <stdio.h>
// Function to recursively search an element in an array
int recursiveSearch(int arr[], int left, int right, int elementToBeSearched)
{
 if (right < left)
 {
 return -1;
 }
 if (arr[left] == elementToBeSearched)
 {
 return left;
 }
 if (arr[right] == elementToBeSearched)
 {
 return right;
 }
 return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched);
}
void printArrayElements(int arr[], int size)
{
 for(int i=0; i<size; i++)
 {
 printf("%d ", arr[i]);
 }
 printf("\⁠n");
}
int main()
{
 int arr1[] = {1, 2, 3, 4, 5, 6, 7};
 int size1 = sizeof(arr1)/sizeof(arr1[0]);
 printf("Array 1: \⁠n");
 printArrayElements(arr1, size1);
 int elementToBeSearched1 = 4;
 printf("Element to be searched: %d \⁠n", elementToBeSearched1);
 int indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1);
 if(indexOfElement1 == -1)
 {
 printf("Element %d not found \⁠n", elementToBeSearched1);
 }
 else
 {
 printf("Element %d found at index %d \⁠n", elementToBeSearched1, indexOfElement1);
 }
int arr2[] = {2, 4, 6, 10, 12, 3, 6};
 int size2 = sizeof(arr2)/sizeof(arr2[0]);
 printf("Array 2: \⁠n");
 printArrayElements(arr2, size2);
 int elementToBeSearched2 = 4;
 printf("Element to be searched: %d \⁠n", elementToBeSearched2);
 int indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2);
 if(indexOfElement2 == -1)
 {
 printf("Element %d not found \⁠n", elementToBeSearched2);
 }
 else
 {
 printf("Element %d found at index %d \⁠n", elementToBeSearched2, indexOfElement2);
 }
int arr3[] = {1, 1, 1, 1, 1};
 int size3 = sizeof(arr3)/sizeof(arr3[0]);
 printf("Array 3: \⁠n");
 printArrayElements(arr3, size3);
 int elementToBeSearched3 = 2;
 printf("Element to be searched: %d \⁠n", elementToBeSearched3);
 int indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3);
 if(indexOfElement3 == -1)
 {
 printf("Element %d not found \⁠n", elementToBeSearched3);
 }
 else
 {
 printf("Element %d found at index %d \⁠n", elementToBeSearched3, indexOfElement3);
 }
 return 0;
}

Output:

Array 1:
1 2 3 4 5 6 7
Element to be searched: 4
Element 4 found at index 3
Array 2:
2 4 6 10 12 3 6
Element to be searched: 4
Element 4 found at index 1
Array 3:
1 1 1 1 1
Element to be searched: 2
Element 2 not found

Learn Recursion

Recursion is a very important and fun programming topic. Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It might be a little difficult to learn for beginner programmers, but learning how to solve problems using recursion is worth it.


Tags
Reactions

Post a Comment

0 Comments