Python program to recursively linearly search elements in an array

Linear search is the simplest way to search for elements in an array. It is a sequential search algorithm that starts from one end and checks each element of the array until the required element is found.

Recursion refers to a function calling itself. When using a recursive function, we need to use any loop to generate the iteration. The syntax below demonstrates how a simple recursive function works.

def rerecursiveFun():
   Statements
   ...   
   rerecursiveFun()
   ...
rerecursiveFun

Linear search for elements recursively

Linear search for an element recursively from an array can only be achieved by using functions. In Python, to define a function, we need to use the def keyword.

In this article, we will learn how to linearly search elements in an array recursively in Python. Here, we will use Python lists instead of arrays since Python does not have a specific data type to represent arrays.

Example

We will recursively call the function recLinearSearch() by decrementing the size of the array. If the size of the array becomes negative, meaning the element is not in the array, we return -1. If a match is found, the index position where the element is located is returned.

# Recursively Linearly Search an Element in an Array  
def recLinearSearch( arr, l, r, x): 
   if r < l: 
      return -1
   if arr[l] == x: 
      return l 
   if arr[r] == x: 
      return r 
   return recLinearSearch(arr, l+1, r-1, x) 
     
lst = [1, 6, 4, 9, 2, 8]
element = 2
res = recLinearSearch(lst, 0, len(lst)-1, element) 
  
if res != -1:
   print('{} was found at index {}.'.format(element, res))
else:
   print('{} was not found.'.format(element))

Output

2 was found at index 4.

Example

Let's look at another example of searching for elements in an array.

# Recursively Linearly Search an Element in an Array  
def recLinearSearch(arr, curr_index, key):
   if curr_index == -1:
      return -1
   if arr[curr_index] == key:
      return curr_index
   return recLinearSearch(arr, curr_index-1, key)
arr = [1, 3, 6, 9, 12, 15]
element = 6
res = recLinearSearch(arr, len(arr)-1, element) 
  
if res != -1:
   print('{} was found at index {}.'.format(element, res))
else:
   print('{} was not found.'.format(element))

Output

6 was found at index 2.

Example

Take searching for element 100 in the array as another example.

# Recursively Linearly Search an Element in an Array  
def recLinearSearch(arr, curr_index, key):
   if curr_index == -1:
      return -1
   if arr[curr_index] == key:
      return curr_index
   return recLinearSearch(arr, curr_index-1, key)     
arr = [1, 3, 6, 9, 12, 15]
element = 100
res = recLinearSearch(arr, len(arr)-1, element) 
  
if res != -1:
   print('{} was found at index {}.'.format(element, res))
else:
   print('{} was not found.'.format(element))

Output

100 was not found.

In the above example, element 100 is not found in the given array.

These are examples of using Python programming to recursively linearly search elements in an array.

The above is the detailed content of Python program to recursively linearly search elements in an array. For more information, please follow other related articles on the PHP Chinese website!