python scooping and recursion

Question

I am struck in a small recursive code. I have printed output and it prints fine but when I try to put a counter to actually count my answers, it gives me scooping errors.

total = 0
def foo(me, t):
    if t<0:
     return
    if t==0:
     total = total+1
     return
    for i in range(1, me+1):
     total = total+1
     return foo(i, t-i)

it says local variable referenced before assignment, well, I am trying to refer total in the first line.... Its not about global variables, I have tried to use global as well but in vain.

This is pure scooping issue, any ideas?

Answer 1

You forgot to make sure to set total as a global in your function. You said "I have tried to use global as well but in vain." but when I try it below it doesn't throw any error:

total = 0
def foo(me, t):
    global total
    if t<0:
        return
    if t==0:
        total = total+1
        return
    for i in range(1, me+1):
        total = total+1
        return foo(i, t-i)

Answer 2

As mentioned by others, you need the global statement for total. Also, as noted by Svante, the for loop is unnecessary as coded since i is always 1. So, with an equivalent version of your code:

total = 0
def foo(me, t):
    global total
    if t < 0:
        return
    total = total + 1
    if t == 0:
        return
    return foo(1, t-1)

foo(99, 100)
print total

It should be easier to see that foo(99, 100) will indeed be 101 since you're essentially counting down from 100 to 0. I'm not sure why you think otherwise?

Answer 3

I'm not sure you really know what you are trying to do... (at least if you say that adding the global keyword gives incorrect results, but silences the errors)

you do need the statement "global total" if you are going to to try to reference total (which you are doing)

(what are you expecting when you execute foo(99, 100)?)

maybe your boundary conditions are wrong?

'cause with the arguments (99, 100)

1. foo will skip the two if statements
2. loop in the following loop:

  for i in range(1, 100):
    total += 1
    return foo(i, 100-i)

which really is equivalent to

  else:
    total += 1
    return foo(1, 99)

(like Svante was saying)

based on your two if conditions foo(1,99) will correctly generate total += 100

(99 times it will execute your "else" statement bringing the total to 100, and then finally it will reach t == 0 and execute the last final if where it will push the total to your "incorrect" 101)

you should also use elif for your second case

Answer 4

As a generic advice, recursion should always use return values, and not global variables. Recursion has already its own load of complexity, increasing it with side-effects and not clear interfaces will make it even worse.

You should try something in the lines of this:

def foo(me, t):
    if t<0:
        return 0
    if t==0:
        return foo(me, t+1)
    return foo(me-1, t)
    for i in range(1, me+1):
        tot =  foo(i, t-i)
    return tot

Note: this code is wrong, it will not solve your problem and it will not even work on its own; I put it just to give a kind of idea of how to design a recursion that is easier to manage.

Answer 5

Thanks people, thanks youarf, Liffredo. I was wrong, I didnt notice that I was returning before adding-up things, loop was only running once, I have fixed the code. It is like this:

def foo(me, t): 
    if t<0:
     return 0
    if t==0:
     return 1
    toreturn = 0
    for i in range(1, me+1):
     toreturn = toreturn + foo(i, t-i)
    return toreturn

This snippet is for this problem at http://projecteuler.net/index.php?section=problems&id=76