CODEWITHSUNDEEP
pythonalgorithmrecursion
Akram Bendoukha
Akram Bendoukha

Reputation: 53

Count the number of opertations inside a recursive algorithm in python

I'm implementing the dichotomic search algorithm in python, in a second version of the function I have to (in addition of returning true or false according to the presence or not of the element) count the number of operations (comparisons) done by the algorithm depending on the length of the list I'm working with and return it.

However, my function is recursive and naturally I'll have to initialize a counter variable (which will be incremented at every operation) to zero. the issue is that this variable will take the zero value at every recursive call and thus, it will not give me the correct value. I thought of a global variable but I don't know how to use it.

Here is the code of my function : 

def trouve(T, x) :      
  if len(T) == 0 :
    return False 
  mid = len(T) // 2
  if T[mid] == x :
    return True
  if len(T) == 1 and T[0] != x  : 
    return False
  else :
    if x > T[mid] :
      return trouve(T[mid:], x)
    else :
      return trouve(T[:mid], x)

Upvotes: 0

Views: 778

Answers (2)

trincot
trincot

Reputation: 350137

Normally, you would count the comparisons of data only, so not the conditions where you compare the length of the input list.

You could use a third argument to accumulate the count, and then let the function return a tuple of both the success and the count:

def trouve(T, x, c = 0):
  if len(T) == 0:
    return (False, c) # len() comparisons do not count 
  mid = len(T) // 2
  if T[mid] == x:
    return (True, c+1)
  if len(T) == 1: # you don't need to compare x again here! 
    return (False, c+1)
  # you don't need `else` here
  if x > T[mid]:
    return trouve(T[mid:], x, c+2)
  # you don't need `else` here
  return trouve(T[:mid], x, c+2)

print (trouve([1,3,8,13,14,15,20], 14))

Note that you can optimise a bit:

def trouve(T, x, c = 0):
  if len(T) == 0:
    return (False, c) 
  mid = len(T) // 2
  # you don't need the `len(T) == 1` case, as it can be 
  # treated in the recursive call. See change below:
  if x > T[mid]:
    return trouve(T[mid+1:], x, c+1) # exclude mid itself
  # Move equality test below greater-then test, since the 
  # equality has little chance of being true:
  if T[mid] == x:
    return (True, c+2)
  return trouve(T[:mid], x, c+2)

print (trouve([1,3,8,13,14,15,20], 14))

... although for the example I gave, the count is still the same in this version.

Upvotes: 1

bytesized
bytesized

Reputation: 1522

If you want to go the global variable route (since you mentioned it), this is how you would do it.

trouve_count = 0
def trouve(T, x) :
  global trouve_count
  # Increment trouve_count like this when necessary:
  trouve_count += 1
  # ...

Be careful using these in larger programs, as you may accidentally use the same global name twice, causing problems.

Upvotes: 0

Related Questions