CODEWITHSUNDEEP
pythonrecursion
jakecar
jakecar

Reputation: 586

Recursion function not working properly

I'm having quite a hard time figuring out what's going wrong here:

class iterate():
    def __init__(self):
        self.length=1
    def iterated(self, n):
        if n==1:
            return self.length
        elif n%2==0:
            self.length+=1
            self.iterated(n/2)
        elif n!=1:
            self.length+=1
            self.iterated(3*n+1)

For example, 

x=iterate()
x.iterated(5)

outputs None. It should output 6 because the length would look like this: 5 --> 16 --> 8 --> 4 --> 2 --> 1

After doing some debugging, I see that the self.length is returned properly but something goes wrong in the recursion. I'm not really sure. Thanks for any help.

Upvotes: 1

Views: 7595

Answers (4)

interjay
interjay

Reputation: 110069

In the two elif blocks, you don't return a value after making the recursive call. You need a return before the recursive calls to iterated (e.g. return self.iterated(n/2)). If you don't explicitly return, the function will return None.

That will fix this issue, but there is a way to make your code simpler: You don't actually need the member length. Instead, you can add 1 to the result of the recursive call:

def iterated(n):
    if n==1:
        return 1
    elif n%2==0:
        return 1 + iterated(n/2)
    else:
        return 1 + iterated(3*n+1)

print(iterated(5))

This doesn't need to be in a class, since there is no need for any members.

Upvotes: 5

President James K. Polk
President James K. Polk

Reputation: 41958

You should finish each elif branch with return self.iterated(...) rather than just self.iterated(...)

Upvotes: 2

Paul Butcher
Paul Butcher

Reputation: 6956

You are only returning a value from the deepest level of recursion, then ignoring it on the second-deepest level.

All of the self.iterated(...) lines should read return self.iterated(...)

Upvotes: 2

Brendan Long
Brendan Long

Reputation: 54242

You're missing the return statements:

class iterate():
    def init(self):
        self.length=1
    def iterated(self, n):
        if n==1:
            return self.length
        elif n%2==0:
            self.length+=1
            **return** self.iterated(n/2)
        elif n!=1:
            self.length+=1
            **return** self.iterated(3*n+1)

Upvotes: 3

Related Questions