CODEWITHSUNDEEP
pythonrecursioncallcallstack
Webtron
Webtron

Reputation: 473

Variable Scope Issue in Python

I am new to Python and I have been working with it for a bit, but I am stuck on a problem. Here is my code:

def collatz(num,ctr):
    if(num != 1):
        ctr+=1
        if(num%2==0):
            collatz(num/2,ctr)
        else:
            collatz(num*3+1,ctr)
    return ctr
test=collatz(9,0)

For any number I put in for num, let's say 9 for instance, and 0 for ctr, ctr always comes out as 1. Am I using the ctr variable wrong?

EDIT: I am trying to print out how many times the function is recursed. So ctr would be a counter for each recursion.

Upvotes: 3

Views: 300

Answers (5)

Chris Gong
Chris Gong

Reputation: 8229

The variable ctr in your example will always be 1 because of the order of the recursive call stack. As one value of ctr is returned, then the call stack will start returning the previous values of ctr. Basically, at the very last recursive call, the highest value of ctr will be returned. But since the method call at the bottom of the call stack returns the very last value aka the value that will be stored in test, test will always be 1. Let's say I input parameters into collatz that would result in five total calls of the method. The call stack would look like this coming down,

collatz returns ctr --> 5
collatz returns ctr --> 4
collatz returns ctr --> 3
collatz returns ctr --> 2
collatz returns ctr --> 1 //what matters because ctr is being returned with every method call

As you can see, no matter how many times collatz is called, 1 will always be returned because the call at the bottom of the call stack has ctr equaling 1.

The solution can be a lot of things, but it really depends on the purpose of what you're trying to accomplish which isn't clearly stated in your question.

EDIT: If you want ctr to end up being the number of times a recursive call is made, then just assign ctr to the value of the method call. It should look like this,

def collatz(num,ctr):
    if(num != 1):
        ctr+=1
        if(num%2==0):
            ctr = collatz(num/2,ctr)
        else:
            ttr = collatz(num*3+1,ctr)
    return ctr
test=collatz(9,0)

Upvotes: 3

hugomg
hugomg

Reputation: 69954

Function parameters in Python are passed by value, not by reference. If you pass a number to a function, the function receives a copy of that number. If the function modifies its parameter, that change will not be visible outside the function:

def foo(y):
   y += 1
   print("y=", y) # prints 11

x = 10
foo(x)
print("x=", x) # Still 10

In your case, the most direct fix is to make ctr into a global variable. Its very ugly because you need to reset the global back to 0 if you want to call the collatz function again but I'm showing this alternative just to show that your logic is correct except for the pass-by-reference bit. (Note that the collatz function doesn't return anything now, the answer is in the global variable).

ctr = 0
def collatz(num):
    global ctr
    if(num != 1):
        ctr+=1
        if(num%2==0):
                collatz(num/2)
        else:
                collatz(num*3+1)

ctr = 0
collatz(9)
print(ctr)

Since Python doesn't have tail-call-optimization, your current recursive code will crash with a stack overflow if the collatz sequence is longer than 1000 steps (this is Pythons default stack limit). You can avoid this problem by using a loop instead of recursion. This also lets use get rid of that troublesome global variable. The final result is a bit more idiomatic Python, in my opinion:

def collats(num):
    ctr = 0
    while num != 1:
        ctr += 1
        if num % 2 == 0:
            num = num/2
         else:
            num = 3*num + 1
    return ctr

print(collatz(9))

If you want to stick with using recursive functions, its usually cleaner to avoid using mutable assignment like you are trying to do. Instead of functions being "subroutines" that modify state, make them into something closer to mathematical functions, which receive a value and return a result that depends only on the inputs. It can be much easier to reason about recursion if you do this. I will leave this as an exercise but the typical "skeleton" of a recursive function is to have an if statement that checks for the base case and the recursive cases:

def collatz(n):
    if n == 1:
        return 0
    else if n % 2 == 0:
        # tip: something involving collatz(n/2)
        return #??? 
    else:
        # tip: something involving collatz(3*n+1)
        return #???

Upvotes: 0

Robert Columbia
Robert Columbia

Reputation: 6418

I changed your recursive calls to set the value received back from the recursive calls into ctr. The way you wrote it, you were discarding the values you got back from recursing.

def collatz(num,ctr):
    if(num != 1):
            ctr+=1
            if(num%2==0):
                    ctr=collatz(num/2,ctr)
            else:
                    ctr=collatz(num*3+1,ctr)
    return ctr

test=collatz(9,0)

Upvotes: 4

Jester
Jester

Reputation: 59

The variable will return the final number of the collatz sequence starting from whatever number you put in. The collatz conjecture says this will always be 1

Upvotes: -3

schoolteacher
schoolteacher

Reputation: 36

An example: 

def collatz(number):

    if number % 2 == 0:
        print(number // 2)
        return number // 2

    elif number % 2 == 1:
        result = 3 * number + 1
        print(result)
        return result

n = input("Give me a number: ")
while n != 1:
    n = collatz(int(n))

Upvotes: 0

Related Questions