Today in this tutorial, we will be finding the first, last, and all occurrences of an element in an array with the help of Recursion.
Before going into any of the problem statements, let us first understand what Recursion is. If you want to learn about Recursion, a link is provided to know about Recursion.
Learn about Recursion here: Python Recursion
Finding the First Occurence of the Element
Let’s begin by looking for the first occurrence of the element in a Python array. We aim to find the very first position at which the element occurs in a list of elements (array).
For Example:
Array Given ==> [1,2,3,4,2]
First Occurence ==> 2
To find the solution to the problem we would take the following steps:
Step 1 : Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then check the first element with X and return the answer if found
Step 3 : For more than one element, we will check if the first element is equal to X if found then return
Step 4 : Otherwise recursively go by slicing the array and incrementing and decremementing the itrerator and n value (size of array ) respectively
Step 5 : Repeat until the element is found or not
The code implementation of the above-mentioned steps is shown below:
def find_first(arr,n,x,itr):
# check if list is empty
if(n==0):
print("List empty!")
return
# Only one element
elif(n==1):
if(arr[0]==x):
print("Element present at position 1")
else:
print("Element not found")
return
# More than one element
else:
if(arr[0] == x):
print("Found at position: ", itr+1)
else:
find_first(arr[1:],n-1,x,itr+1)
return
arr = [1,2,3,4,5,2,10,10]
n = len(arr)
x = 10
itr = 0
find_first(arr,n,x,itr)
Output:
Found at position: 7
Finding the Last Occurence of an Object
Next, we’ll try to find the last occurrence of the element using Python. We aim to find the very last position at which the element occurs in a list of elements (array).
For Example:
Array Given ==> [1,2,3,4,2]
Last Occurence ==> 5
To find the solution to the problem we would take the following steps:
Step 1 : Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then check the first element with X and return the answer if found
Step 3 : For more than one element, we will check if the last element is equal to X if found then return
Step 4 : Otherwise recursively go by slicing the array and decremementing both the iterator and n value (size of array )
Step 5 : Repeat until the element is found or not
Implementing the above steps in Python
def find_first(arr,n,x,itr):
# check if list is empty
if(n==0):
print("List empty!")
return
# Only one element
elif(n==1):
if(arr[0]==x):
print("Element present at position 1")
else:
print("Element not found")
return
# More than one element
else:
if(arr[n-1] == x):
print("Found at position: ", itr+1)
else:
find_first(arr[:-1],n-1,x,itr-1)
return
arr = [1,2,3,4,5,2,3,2,3,2,10,10]
n = len(arr)
x = 2
itr = n - 1
find_first(arr,n,x,itr)
Output:
Found at position: 10
Finding All Occurences of an Object
Here we aim to find all the positions at which the element occurs in a list of elements (array). The occurrences include the first, last, and any middle positions of the element in the array.
For Example:
Array Given ==> [1,2,3,4,2]
All Occurences ==> 2 5
To find the solution to the problem we would take the following steps:
Step 1 : Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then print the position of the element and return
Step 3 : For more than one element, we will check if the first element is equal to X if found then print and keep on recursively calling the function again by slicing the array and decremementing n value (size of array ) and incrementing the value of iterator
Step 5 : Repeat until all the elements are encountered.
Implementing the above steps in Python
def find_first(arr,n,x,itr):
# check if list is empty
if(n==0):
print("List empty!")
return
# Only one element
elif(n==1):
if(arr[0]==x):
print(itr+1,end=" ")
else:
print("Element not found")
# More than one element
else:
if(arr[0] == x):
print(itr+1,end=" ")
find_first(arr[1:],n-1,x,itr+1)
arr = [1,2,10,3,4,10,5,2,10,2,3,10]
n = len(arr)
x = 10
itr = 0
print("Found at position: ",end="")
find_first(arr,n,x,itr)
Output:
Found at position: 3 6 9 12
Conclusion
So by end of this tutorial, we are familiar with finding an elements’ first, last, and all occurrences in a given array. Hope you understood the logic!
Thank you for reading! Happy learning! 😇