Python: variable bindings in recursive functions

Question

I came across some weirdness in Python using a function similar to the following:

    def foo(x):
        if int(x)!=4:
            x = raw_input("Wrong guess, please enter new value: " )
            foo(x)
        else:
            print "Good Job! %s was right"%x
        return x

    value = foo(x=raw_input("Guess a Number between 1 and 10: "))
    print value

If I enter, for instance: "1" then "2" then "3" then "4", I get the following printed out:

Good Job! 4 was right
2

This is confusing, since it seems the function is successfully identifying the right answer, but after doing so it is returning a value that was the 2nd response given, instead of the most recent response.

Can anyone explain what's going on with the binding of "x" in this recursive function?

Related: [Asking the user for input until they give a valid response](http://stackoverflow.com/questions/23294658/asking-the-user-for-input-until-they-give-a-valid-response) — Kevin, Aug 25 '14 at 17:58

score 4 · Accepted Answer · answered Aug 25 '14 at 17:55

Let's see!

value = foo(raw_input())
# foo is the same as in the question, I won't repeat it here
print value

Inside your foo, you get this:

# foo(1) calls foo(2) and sets x to 2
# foo(2) calls foo(3) and sets x to 3
# foo(3) calls foo(4) and sets x to 4
# foo(4) does:
print "Good Job! 4 was right"
return 4 # to foo(3)
# foo(3) does:
return 4 # to foo(2)
# foo(2) does:
return 3 # to foo(1)
# foo(1) does:
return 2 # to main

Since the return value to main (from the outermost recursion) is 2, that's what value remains.

To fix this, you can either make it iterative:

def iter_foo(x):
    while int(x) != 4:
        x = raw_input("Wrong guess. Try again! ")
    print "Good Job! %s was right" % x
    return x

Or make EACH recursion return the result of the new function

def recurse_foo(x):
    if int(x) != 4:
        return foo(raw_input("Wrong guess. Try again! "))
    else:
        print "Good Job! %s was right!" % x
        return x

Accepting this for the two workarounds provided, and a good explanation of how the foo() executions call each other. The other answers are helpful too, I now understand how the recursive calls are working — arkansasred, Aug 25 '14 at 21:08

score 3 · Answer 2 · answered Aug 25 '14 at 17:54

So it's mostly because you are missing a return in

def foo(x):
    if int(x)!=4:
        x = raw_input("Wrong guess, please enter new value: " )
        foo(x) # <-- need return
    else:
        print "Good Job! %s was right"%x
    return x

value = foo(x=raw_input("Guess a Number between 1 and 10: "))
print value

What's happening is it calls foo(1), which is not equal to 4, assigns x to 2, and that is the last value that x gets assigned to, so

Your recursive foo(x) returns a value, but it isn't assigned to anything or returned from the recursive call.
The last value x received was 2, so that is what the initial foo(1) returns

So either

x = foo(x)

Or

return foo(x)

On the line I highlighted

score 2 · Answer 3 · answered Aug 25 '14 at 18:04

Try the following code:

def foo(x):
    if int(x)!=4:
        x = raw_input("Wrong guess, please enter new value: " )
        return foo(x)
    else:
        print "Good Job! %s was right"%x
        return x

value = foo(x=raw_input("Guess a Number between 1 and 10: "))
print value

You can think each call to the function foo, creates a new variable x. Thus, the recursive calls make a sequence of variables x1, x2, x3, etc. Thus when a function call returns, your local variable x is unchanged. That's why you still get 2 instead of the assignment from the last recursive call (4). If you want to change the variable passed into a function, you need to pass it by reference (or object), rather than by value. [See this article for more details: http://uvesway.wordpress.com/2013/02/18/passing-arguments-to-a-function-by-value-by-reference-by-object/]

You probably should mention that, as Python does not have [tail call optimization](http://en.wikipedia.org/wiki/Tail_call), using recursion here could lead to stack overflow. — Sylvain Leroux, Aug 25 '14 at 18:47

Python: variable bindings in recursive functions

3 Answers3