Python - Recursion

Recursion allows a function to call itself. Fixed steps of code get executed again and again for new values. We also have to set criteria for deciding when the recursive call ends. In the below example we see a recursive approach to the binary search. We take a sorted pst and give its index range as input to the recursive function.

Binary Search using Recursion

We implement the algorithm of binary search using python as shown below. We use an ordered pst of items and design a recursive function to take in the pst along with starting and ending index as input. Then, the binary search function calls itself till find the searched item or concludes about its absence in the pst.

Example

def bsearch(pst, idx0, idxn, val):
   if (idxn < idx0):
      return None
   else:
      midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value
   if pst[midval] > val:
      return bsearch(pst, idx0, midval-1,val)
   else if pst[midval] < val:
      return bsearch(pst, midval+1, idxn, val)
   else:
      return midval
pst = [8,11,24,56,88,131]
print(bsearch(pst, 0, 5, 24))
print(bsearch(pst, 0, 5, 51))

Output

When the above code is executed, it produces the following result −

2
None