CODEWITHSUNDEEP
python
ihf
ihf

Reputation: 91

eliminate global variable from recursive function

I wrote this very simple function to count the steps for the Collatz series to converge to 1. It is called recursively but uses a global variable which I would like to eliminate. I believe that the proper(?) way to do this is to make the variable a parameter of the function call; however, when I did this I got the value after the calls were all unwound rather than the last value. For example, if you call this function with steps = 0; collatz(97), you will get 118 returned.

def collatz(num):
    global steps
    steps += 1
    if num == 1:
        return
    if num % 2 == 0:
        num = num / 2
    else:
        num = 3 * num + 1
    collatz(num)
    return (steps - 1)

With a parameter for the variable steps:

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

collatz(97,0) returns 0. I know I am overlooking something but what?

Upvotes: 1

Views: 49

Answers (2)

user2390182
user2390182

Reputation: 73490

The local variable steps is immutable. The recursive call will not be able to magically modify or rebind it, nor has the recursive function call any access to the surrounding scope. You have to communicate recursive intermediate results via the return value. Try the following:

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

>>> collatz(97)
118

Upvotes: 1

Joe Iddon
Joe Iddon

Reputation: 20434

No global needed, each function returns the steps required from that sequence onwards plus 1, where the base case (num == 1) returns 0:

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

e.g.

>>> collatz(97)
118

Upvotes: 3

Related Questions