C Program to Implement Linear Search using Recursion

This is a C Program to implement Linear Search Algorithm using Recursion.

Problem Description

We have to create a C Program which finds the position of an element in an array using Linear Search Algorithm using Recursion.

Expected Input and Output

1. Average Case : On an average, linear search takes O(n) comparisons to find the position of the element. For example:

If the input array has data as {4, 6, 1, 2, 5, 3}
and element to be searched is 6,
then the expected output will be Position 2

Average case time complexity : O(n)

2. Best Case: When the key we have to search is the first element of array, we have to make just one comparison. For example:

If the input array has data as {66, -3, 31}
and element to be searched is 66
then the expected output will be Position 1

Best case time complexity : O(1)

3. Worst Case: When the key to be searched for is the last element of an array, the algorithm has to traverse the whole array element by element in order to look for the key. For example:

If the input array has data as {1, 3, 6, 1, 9}
and element to be searched is 9
then the expected output will be Position 5

Worst case time complexity : O(n)

Note: Join free Sanfoundry classes at Telegram or Youtube

Problem Solution

1. We first have to create an array of numbers by taking input from user.
2. We have to input an array of numbers and then apply the linear search algorithm to find the position of an element in an array, if it exists.
3. In order to look for an element in an array, we’ll go sequentially in increasing index values.
4. If we encounter the element requested by the user we will return the position of that element in array, but if it is not there we will return -1 which indicates the absence of element which was searched.

Program/Source Code

Here is the source code of the C Program to implement Linear Search Algorithm on array of numbers using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

/* C Program to implement Linear Search Algorithm recursively */

```
 
```
```
#include <stdio.h>
```

int RecursiveLS(int arr[], int value, int index, int n)

```
{
```
```
    int pos = 0;
```
```
 
```
```
    if(index >= n)
```
```
    {
```
```
        return 0;
```
```
    }
```
```
 
```
```
    else if (arr[index] == value)
```
```
    {
```
```
        pos = index + 1;
```
```
        return pos;
```
```
    }
```
```
 
```
```
    else
```
```
    {
```

        return RecursiveLS(arr, value, index+1, n);

```
    }
```
```
    return pos;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n, value, pos, m = 0, arr[100];
```

    printf("Enter the total elements in the array  ");

```
    scanf("%d", &n);
```
```
 
```

    printf("Enter the array elements\n");

```
    for (int i = 0; i < n; i++)
```
```
    {
```
```
        scanf("%d", &arr[i]);
```
```
    }
```
```
 
```

    printf("Enter the element to search  ");

```
    scanf("%d", &value);
```
```
 
```

    pos =  RecursiveLS(arr, value, 0, n);

```
    if (pos != 0)
```
```
    {
```

        printf("Element found at pos %d ", pos);

```
    }
```
```
    else
```
```
    {
```
```
        printf("Element not found");
```
```
    }
```
```
    return 0;
```
```
}
```

Program Explanation

1. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
2. The array is searched sequentially and the position is returned if the key element to be searched is available in the array, otherwise “Element not found” is printed.
3. Here in this C Program we have created a recursive function called RecursiveLS(), which takes in 4 input parameters and returns the position of element in a array which is searched by the user.
4. If the element that is searched is the first we directly return the index.
5. But if it is not the first element of array, we decrease the size of array by 1, by eliminating the first element of the array, which means when the RecursiveLS() is called second time the array size will be (n-1). This will go on until the element is found.

Runtime Test Cases

Test case 1 – Average case (Element to be searched is at random location in the array).

   Enter the total elements in the array  6
   Enter the array elements
   4
   6
   1
   2
   5
   3
   Enter the element to search  6
   Element found at pos 2

Test case 2 – Best case (Element to be searched is at 1st position itself).

   Enter the total elements in the array  3
   Enter the array elements
   66
   -3
   31
   Enter the element to search  66
   Element found at pos 1

Test case 3 – Worst case (Element to be searched is at the end of the array).

   Enter the total elements in the array  5
   Enter the array elements
   1
   3
   6
   1
   9
   Enter the element to search  9
   Element found at pos 5

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement the Schonhage-Strassen Algorithm for Multiplication

» Next - C Program to Implement Affine Cipher

Related Posts:

Apply for C Internship
Practice Computer Science MCQs
Check C Books
Apply for Computer Science Internship
Practice BCA MCQs

Recommended Articles: