Drew Ackerman - 4 months ago 6
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):

# 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
Dividing two...
25.0
Subtracting one now...
24.0
Dividing three...
8.0
Dividing two...
4.0
Dividing two...
2.0
Dividing two...
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

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

``````def efficientalgo(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)
Dividing two...
50.0
Dividing two...
25.0
Subtracting one now...
24.0
Dividing three...
8.0
Dividing two...
4.0
Dividing two...
2.0
Dividing two...
1.0
Out[4]: 1.0
``````

Or simply return:

``````def efficientalgo(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
``````
Source (Stackoverflow)