Is this an issue with my method of recursion?

Question

In response to this question I tried to come up with my own solution.

My solution in python 3.X

def efficientalgo(number, x):
    print("Start with this number... " + str(number))

    # See if a number is dividable by three, if so then divide by 3
    if number % 3 == 0:
        print("Dividing three...")
        number /= 3
        print(number)
        # use recursion to see if the number can be divided again
        number += efficientalgo(number, x)
        print("Returning number from division by three now...")
        return number


   # Divide a number by 2 if it is evenly dividable by 2
   if number % 2 == 0:
        print("Dividing two...")
        number /= 2
        print(number)
        # Use recursion to see if the number can be divided again
        number += efficientalgo(number, x)
        print("Returning number from division by two now...")
        print(number)
        return number


    # If a number is not one, then subtract one and call the
    if number != 1:
        print("Subtracting one now...")
        number -= 1
        print(number)
        # Use recursion to see if the number can be divided again
        number += efficientalgo(number, x)
        print(number)
        return number

    # If the number is one, return it and finish.
    if number == 1:
        print("Returning one now... " + str(number))
        return number

print(efficientalgo(100, 1))

Here is a "working" pythonfiddle

The output

Start with this number... 100
Dividing two...
50.0
Start with this number... 50.0
Dividing two...
25.0
Start with this number... 25.0
Subtracting one now...
24.0
Start with this number... 24.0
Dividing three...
8.0
Start with this number... 8.0
Dividing two...
4.0
Start with this number... 4.0
Dividing two...
2.0
Start with this number... 2.0
Dividing two...
1.0
Start with this number... 1.0
Returning one now... 1.0
-----Above this line is the correct output I want-----

---------Below this line, I have no idea what is going on--------
Returning number from division by two now...
2.0
Returning number from division by two now...
4.0
Returning number from division by two now...
8.0
Returning number from division by three now...
40.0
Returning number from division by two now...
65.0
Returning number from division by two now...
115.0
115.0

As you can see, i have implemented my recursion incorrectly and am getting some sort of feedback loop where in the program gets down to the correct answer, then keeps going after ive returned my final number, which in this case is a one.

I do not understand what is happening below the Lines i have marked out in the output

Some of your `if` blocks aren't returning anything, so you return `None` instead of a value. — Barmar, Jun 10 '16 at 23:40
See http://stackoverflow.com/questions/27691547/recursive-function-does-not-return-specified-value — Barmar, Jun 10 '16 at 23:40
I got the whole code to run with no errors just by changing some indentations. What is the code supposed to output? — Keatinge, Jun 10 '16 at 23:40
The Code has been changed to include returns, if you copy and paste it you'll see that it indeed resolves to one, then it starts be behave very wildly. You'll see it print out the returned values. Removing the returns in the If statements gets rid of that weird behavior, but then adds the errors I mentioned in the post. — Drew Ackerman, Jun 10 '16 at 23:51
@PadraicCunningham Although a little more elegant, and less explicit, it effectively changes nothing. — Drew Ackerman, Jun 11 '16 at 00:01
Why are you += number and then expecting 1 to be returned? Add what the code is supposed to be doing — Padraic Cunningham, Jun 11 '16 at 00:05
@PadraicCunningham I am trying to solve the issue that is related to the first link. I am also trying to do it recursively. Im not entirely sure why i use +=, its just what Ive seen in examples and it does partly work. — Drew Ackerman, Jun 11 '16 at 00:10

Padraic Cunningham · Accepted Answer · 2016-06-11T00:20:26.660

number should be set = efficientalgo(..) to not +=:

def efficientalgo(number):
    print("Start with this number... " + str(number))
    # See if a number is dividable by three, if so then divide by 3
    if number % 3 == 0:
        print("Dividing three...")
        number /= 3
        print(number)
        # use recursion to see if the number can be divided again
        number =  efficientalgo(number)
    # Divide a number by 2 if it is evenly dividable by 2
    if number % 2 == 0:
        print("Dividing two...")
        number /= 2
        print(number)
        # Use recursion to see if the number can be divided again
        number = efficientalgo(number)

    # If a number is not one, then subtract one and call the
    if number != 1:
        print("Subtracting one now...")
        number -= 1
        print(number)
        # Use recursion to see if the number can be divided again
        number = efficientalgo(number)
   return number

Once you do that you get the expected output:

In [4]: efficientalgo(100)
Start with this number... 100
Dividing two...
50.0
Start with this number... 50.0
Dividing two...
25.0
Start with this number... 25.0
Subtracting one now...
24.0
Start with this number... 24.0
Dividing three...
8.0
Start with this number... 8.0
Dividing two...
4.0
Start with this number... 4.0
Dividing two...
2.0
Start with this number... 2.0
Dividing two...
1.0
Start with this number... 1.0
Out[4]: 1.0

Or simply return:

def efficientalgo(number):
    print("Start with this number... " + str(number))
    # See if a number is dividable by three, if so then divide by 3
    if number % 3 == 0:
        print("Dividing three...")
        number /= 3
        print(number)
        # use recursion to see if the number can be divided again
        return efficientalgo(number)

    # Divide a number by 2 if it is evenly dividable by 2
    if number % 2 == 0:
        print("Dividing two...")
        number /= 2
        print(number)
        # Use recursion to see if the number can be divided again
        return efficientalgo(number)

    # If a number is not one, then subtract one and call the
    if number != 1:
        print("Subtracting one now...")
        number -= 1
        print(number)
        # Use recursion to see if the number can be divided again
        return efficientalgo(number)

    return number

I still get the same issue of that strange continuation after the code gets down to 1. — Drew Ackerman, Jun 11 '16 at 00:18
@DrewAckerman, what you see in my output is what the functions outputs, if you see something different then you must have done something different — Padraic Cunningham, Jun 11 '16 at 00:22
Your second solution of returning the function works. Why Though? If you could also help me with figuring out the big O complexity, thatd be great too. — Drew Ackerman, Jun 11 '16 at 00:33

Is this an issue with my method of recursion?

My solution in python 3.X

The output

1 Answers1