# Recursive program to linearly search an element in a given array

• Difficulty Level : Basic
• Last Updated : 15 Jul, 2022

Given an unsorted array and an element x, search x in the given array. Write recursive C code for this. If the element is not present, return -1.

Approach : The idea is to compare x with the last element in arr[]. If the element is found at the last position, return it. Else recur searchElement() for remaining array and element x.

## C++

 `/*`` ``* Approach : The idea is to compare x with the last element`` ``* in arr[]. If the element is found at the last position,`` ``* return it. Else recur searchElement() for remaining array and`` ``* element x.`` ``*/``  ` `  ` `#include `` ` `using` `namespace` `std;`` ` `// Recursive function to search for x in arr[]``int` `searchElement(``int` `arr[], ``int` `size, ``int` `x) {``     ` `    ``size--;``     ` `    ``// Base case (Element not present in the array)``    ``if` `(size < 0) {``        ``return` `-1;``    ``}``    ``// Base case (Element found, return its position)``    ``if` `(arr[size] == x) {``        ``return` `size;``    ``}`` ` `    ``// Recursive case``    ``return` `searchElement(arr, size, x);`` ` `}`` ` ` ` `// Driver code``int` `main() {``    ``int` `arr[] = {17, 15, 11, 8, 13, 19};``    ``int` `size = ``sizeof``(arr) / ``sizeof``(arr);``    ``int` `x = 11;``    ``int` `idx = searchElement(arr, size, x);``    ``if` `(idx != -1) ``        ``cout << ``"Element "` `<< x << ``" is present at index "` `<

## C

 `/* `` ``* Approach : The idea is to compare x with the last element in arr[].`` ``* If an element is found at the last position, return it.`` ``* Else recur elmntSrch() for remaining array and element x. `` ``*/`` ` `#include `` ` `// Recursive function to search x in arr[]``int` `elmntSrch(``int` `arr[], ``int` `size, ``int` `x) {``    ``int` `rec;`` ` `    ``size--;`` ` `    ``if` `(size >= 0) {``        ``if` `(arr[size] == x)``            ``return` `size;``        ``else``            ``rec = elmntSrch(arr, size, x);``    ``}``    ``else``        ``return` `-1;`` ` `    ``return` `rec;``}`` ` `int` `main(``void``) {``    ``int` `arr[] = {12, 34, 54, 2, 3};``    ``int` `size = ``sizeof``(arr) / ``sizeof``(arr);``    ``int` `x = 3;``    ``int` `indx;`` ` `    ``indx = elmntSrch(arr, size, x);`` ` `    ``if` `(indx != -1)``        ``printf``(``"Element %d is present at index %d"``, x, indx);``    ``else``        ``printf``(``"Element %d is not present"``, x);`` ` `    ``return` `0;``}`` ` `// This code is contributed by Manish Kumar (mkumar2789)`

## Java

 `// Recursive Java program to search x in array``class` `Test``{``     ``static` `int` `arr[] = {``12``, ``34``, ``54``, ``2``, ``3``};``      ` `     ``/* Recursive Method to search x in arr[l..r] */``     ``static` `int` `recSearch(``int` `arr[], ``int` `l, ``int` `r, ``int` `x)``     ``{``          ``if` `(r < l)``             ``return` `-``1``;``          ``if` `(arr[l] == x)``             ``return` `l;``          ``if` `(arr[r] == x)``             ``return` `r;``          ``return` `recSearch(arr, l+``1``, r-``1``, x);``     ``}``      ` `     ``// Driver method``     ``public` `static` `void` `main(String[] args) ``     ``{``        ``int` `x = ``3``; ``         ` `        ``//Method call to find x``        ``int` `index = recSearch(arr, ``0``, arr.length-``1``, x);``        ``if` `(index != -``1``)``           ``System.out.println(``"Element "` `+ x + ``" is present at index "` `+ ``                                                    ``index);``        ``else``            ``System.out.println(``"Element "` `+ x + ``" is not present"``);``        ``}`` ``}`

## Python3

 `# Recursive function to search x in arr[l..r] ``def` `recSearch( arr, l, r, x):``    ``if` `r < l:``        ``return` `-``1``    ``if` `arr[l] ``=``=` `x:``        ``return` `l``    ``if` `arr[r] ``=``=` `x:``        ``return` `r``    ``return` `recSearch(arr, l``+``1``, r``-``1``, x)`` ` `# Driver Code ``arr ``=` `[``12``, ``34``, ``54``, ``2``, ``3``]``n ``=` `len``(arr)``x ``=` `3``index ``=` `recSearch(arr, ``0``, n``-``1``, x)``if` `index !``=` `-``1``:``    ``print` `(``"Element"``, x,``"is present at index %d"` `%``(index))``else``:``    ``print` `(``"Element %d is not present"` `%``(x))`` ` `# Contributed By Harshit Agrawal`

## C#

 `// Recursive C# program to ``// search x in array``using` `System;`` ` `static` `class` `Test``{``    ``static` `int` `[]arr = {12, 34, 54, 2, 3};``     ` `    ``/* Recursive Method to search x in arr[l..r] */``    ``static` `int` `recSearch(``int` `[]arr, ``int` `l, ``int` `r, ``int` `x)``    ``{``        ``if` `(r < l)``            ``return` `-1;``        ``if` `(arr[l] == x)``            ``return` `l;``        ``if` `(arr[r] == x)``            ``return` `r;``        ``return` `recSearch(arr, l+1, r-1, x);``    ``}``     ` `    ``// Driver method``    ``public` `static` `void` `Main(String[] args) ``    ``{``        ``int` `x = 3; ``         ` `        ``// Method call to find x``        ``int` `index = recSearch(arr, 0, arr.Length-1, x);``         ` `        ``if` `(index != -1)``        ``Console.Write(``"Element "` `+ x + ``                      ``" is present at index "` `+ index);``        ``else``            ``Console.Write(``"Element "` `+ x + ``                          ``" is not present"``);``        ``}``}`` ` `// This code is contributed by Smitha Dinesh Semwal`

## PHP

 ``

## Javascript

 ``

Output

`Element 11 is present at index 2`

Explanation

We iterate through the array from the end by decrementing the size variable and recursively calling the function searchElement(). If the size variable becomes less than zero it means the element is not present in the array and we return -1. If a match is found, we return the size variable which is the index of the found element. This process is repeated until a value is returned to main().

It is important to note that if there are duplicate elements in the array, the index of the last matched element will be returned since we are (recursively) iterating the array from the end.

Time Complexity: O(N), where N is the size of the given array.
Auxiliary Space: O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

My Personal Notes arrow_drop_up