Count the number of opertations inside a recursive algorithm in python

Question

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)

The only operation you count as comparison is `x > T[mid]`? What is - according to you a comparison? — Willem Van Onsem, Feb 25 '17 at 19:31
why not define a [global var](http://stackoverflow.com/questions/423379/using-global-variables-in-a-function-other-than-the-one-that-created-them) (*gasp*) and increment it? — Nullman, Feb 25 '17 at 19:43
you could also try a ["static"](http://stackoverflow.com/questions/279561/what-is-the-python-equivalent-of-static-variables-inside-a-function) — Nullman, Feb 25 '17 at 19:45
@Nullman OP said, "I thought of a global variable but I don't know how to use it." — bytesized, Feb 25 '17 at 19:45
@bytesized ahh yes, you are correct. i amended my suggestion to include a link — Nullman, Feb 25 '17 at 19:47

trincot · Accepted Answer · 2017-02-25T19:50:01.830

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.

score 0 · Answer 2 · answered Feb 25 '17 at 19:47

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.

Count the number of opertations inside a recursive algorithm in python

2 Answers2