Counting the number of executed operations over the same input for a recursive call

Asked

Viewed 75 times

1

idea: Compare a recursive version of the exponentiation implementation with a non-recursive version.

Recursive version:

def power(base,expoente):
    global cont

    if base == 1:
        return 1
    elif expoente == 0:
        return 1
    else:
        cont +=1
        return base*power(base,expoente-1), cont

#print(power(1,1000))
print(power(3,4))

The variable cont would count the number of multiplications. I’m getting the bug: 

NameError: name 'cont' is not defined

although it is a variable defined as global. What is wrong? How to count the number of multiplications performed?

python python-3.x recursion

2 answers

3


This error is being generated on the line where you try the code cont += 1, because nowhere in the code did you initialize this variable.

Corrected code:

cont = 0

def power(base,expoente):
    global cont

    if base == 1:
        return 1
    elif expoente == 0:
        return 1
    else:
        cont +=1
        return base*power(base,expoente-1)

#print(power(1,1000))
print(power(3,4))

Problem found in your code:

Note that in the code above I removed the return of the variable cont. I did this because I don’t think it necessary to return a variable that is global and because the return of cont was causing a problem for your code.

Basically, when returning the cont, you multiplied a tuple, because the function would return two values. Soon the output of the code was this:

((((3, 4, 3, 4, 3, 4), 4, (3, 4, 3, 4, 3, 4), 4, (3, 4, 3, 4, 3, 4), 4), 4, ((3, 4, 3, 4, 3, 4), 4, (3, 4, 3, 4, 3, 4), 4, (3, 4, 3, 4, 3, 4), 4), 4, ((3, 4, 3, 4, 3, 4), 4, (3, 4, 3, 4, 3, 4), 4, (3, 4, 3, 4, 3, 4), 4), 4), 4)

When should this be:

81

Improved code:

def power(base, expoente):
    if base == 1 or not expoente:
        return 1
    else:
        return base * power(base, expoente - 1)

If the variable cont is not used during the execution of the function, I see no need to create it, as it will have the same value as the expoente.

  • But my logic of counting multiplications is correct?

  • 1

    Your logic is correct but your code has a problem. You are multiplying a tuple because its function returns two values, one of them being the variable cont. To solve this problem I withdrew the return of cont, because it doesn’t make much sense to return a variable that is global right.

  • When I print cont, in the end, it comes to zero... there’s something wrong!

  • For me it gives four. You can copy and put the code exactly like this in my reply to check ?

  • where part of the code I can print the content value?

  • After function call. If you print before, the output will actually be zero because the variable would not have been changed.

  • My recursive code is wrong: The multiplication count is the same as in the non-recursive version. Any suggestions to improve it?

  • Regarding logic no but you can give a simplified in it, I will edit the answer.

Show 3 more comments

2

The variable cont is defined as global, but you must initialize it beforehand:

def power(base,expoente):
    global cont
    cont = 0
    if base == 1:
        return 1
    elif expoente == 0:
        return 1
    else:
        cont +=1
        return base*power(base,expoente-1), cont

print(power(3,4))

  • But my logic of counting multiplications is correct?

Browser other questions tagged python python-3.x recursion

You are not signed in. Login or sign up in order to post.