python - Recursion function not working properly

1
votes

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.

4
pythonrecursion
I'm curious, what version of Python are you using? I usually use Python 2.6 and init needs to be declared as init. But this clearly runs for you, so I'm wondering what version of Python allows this - inspectorG4dget
@inspectorG4dget - The provided source code had double underscores around the init, but they were originally removed by the formatting and not displayed (which I'm guessing is what also happened to your comment). I've fixed the formatting for the question now. - ire_and_curses
@ire_and_curses: So it seems. Looks like the double underscore is the text are formatting for bold! - inspectorG4dget

4 Answers

5
votes

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.

3
votes

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)
2
votes

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(...)

2
votes

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