Python recursion function issue

Question

I am python beginner and at the moment I am struggling with python recursion function:

x = 10
n = 3


def rec(x,n):
    if n>0:
        #global x2
        x2 = x*n
        return rec(x2,n-1)
    else:
        return x2

# function call:
fcall = rec(x,n)

print fcall

What confuses me is that global x2 line. With it, the function is working fine returns 60 as expected, but without it I am getting an error message:

Local variable 'x2' referenced before assignment

Why is that so? Seems like once n reaches value of 3, and the else condition gets executed, it does not know what x2 is?

An answer can be found here: [UnboundLocalError in Python](http://stackoverflow.com/questions/9264763/unboundlocalerror-in-python) — , Dec 26 '13 at 23:37
Voting to delete because, aside from the *described problem* being a common duplicate, the *approach to the code shown* does not make sense. — Karl Knechtel, Sep 09 '22 at 11:18

score 2 · Answer 1 · answered Dec 26 '13 at 23:45

If you leave out the global, then the variable is expected to be in local scope within that function. That means that it needs to be assigned somewhere to actually exist. As the only assignment is when the n > 0 condition is true, the return x2 will always try to return a variable that does not exist.

When you add the global, you put that variable into the global scope, making it available everywhere. So it’s assigned and can be returned.

However, it’s not really a good idea to have a function depend on a global variable like that. It seems very unobvious that a global variable is required for it to work. And in fact, it’s not necessary here: Instead of x2 you want to reference x.

def rec (x, n):
    if n > 0:
        x = x * n
        return rec(x, n - 1)
    else:
        return x

That way, as long as n is still bigger than zero, you multiply the current x by n and temporarily assign it to x again, which you then pass to the recursive call. If n is equal to zero, then the else case applies, and you just return the current x that was passed to the function.

Thank you for the reply. It is interesting that when checking out tutorials on global vs local variables, they always present you an example on a simple (not recursive function). So the part that is left is that: local function in recursive function is local in the scope, of only that current recurse (if I may use that term) not in all of the recurses (ah, even worst term, sorry)? — marco, Dec 27 '13 at 00:04
Local variables in a function are only visible to the current execution of that function yes. So if you want to carry over any value to the next recursion, you will have to pass those values in the recursive call. — poke, Dec 27 '13 at 00:20

score 1 · Answer 2 · edited Apr 12 '17 at 07:31

Without global x2, assigning to x2 creates a new local variable. With it, assigning to x2 makes it change the global x2 variable. This applies only to assignment, not to looking up variables.

The current stack frame (and thus all local variables associated with it) disappears when the function returns, but globals stay forever and ever and ever (and you should also feel very bad for using them).

score 1 · Accepted Answer · answered Dec 26 '13 at 23:43

1

Your problem is that x2 is only a local variable, so when you call the function it doesn't know the old x2 anymore.

By adding the global x2 you put that variable in the global space, so now the function can recognise it.

Check this out: http://gettingstartedwithpython.blogspot.de/2012/05/variable-scope.html

What you actually want to return is x, not x2, because you are passing the value of x2 into the next call of your recursion.

def rec(x,n):
    if n>0:
        x2 = x*n
        return rec(x2,n-1)
    else:
        return x

answered Dec 26 '13 at 23:43

isset

2,093
1
13
14

Thank you Isset. So basically the `x` that gets returned from `else` is the last `x2` that was passed in as the argument to the rec() function? – marco Dec 27 '13 at 00:12
1

That's right. That's the Magic of recursion :). The x'es bubble down until the "break"-condition is hit. Than they go all the way up. – isset Dec 27 '13 at 00:53
yea, but that looks like a rocket science to us, non-programers – marco Dec 27 '13 at 01:16

score 1 · Answer 4 · answered Dec 27 '13 at 00:00

1

And also you can refactor your rec function code to:

def rec(x, n):
    return rec(x*n, n-1) if n else x

answered Dec 27 '13 at 00:00

Omid Raha

9,862
1
60
64

What will it do if n is negative? – dansalmo Dec 27 '13 at 00:07
I think, it assumed that n always is >=0, otherwise to prevent to maximum recursive error, condition of if must be `if n>0`. – Omid Raha Dec 27 '13 at 00:12

score 1 · Answer 5 · answered Dec 27 '13 at 00:10

1

A typical cause of problems for beginning programmers is the habit of using too many variables. This can make things more complicated and harder to understand. Your code can be made simpler like this:

def rec(x, n):
   if n > 0:
       return rec(x*n, n-1)
   return x

or even this, using the ternary operator:

def rec(x, n):
   return rec(x*n, n-1) if n > 0 else x

You can then try it out by just doing:

rec(3, 10)

The sooner you can build a habit creating new variables only when they are needed or improve the readability of the code, the easier your programs will be to write, debug and read.

answered Dec 27 '13 at 00:10

dansalmo

11,506
5
58
53

Thank you for the reply dansalmo. I am not even a programmer, neither I intend doing it for living. But I think learning at least one programming language is something that is more than desirable in these years. I chose Python. As I do not intend to become a professional, I will stick with 2 variables in this case - it will enable me to realize what exactly is going on, and what is passed. Rather than just using/passing one variable inside of function. At least that's what I am still trying to figure out in that Isset's reply. – marco Dec 27 '13 at 00:19

Python recursion function issue

5 Answers5