CODEWITHSUNDEEP
pythonrecursionbig-o
Drew Ackerman
Drew Ackerman

Reputation: 341

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

Upvotes: 1

Views: 61

Answers (1)

Padraic Cunningham
Padraic Cunningham

Reputation: 180481

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

Upvotes: 1

Related Questions