Drew Ackerman Drew Ackerman - 5 months ago 7
Python Question

Is this an issue with my method of recursion?

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

Answer

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