Pouring water between two jugs to get a certain amount in one of the jugs (2) I have been practicing recursion lately and I came up with this code to solve the water jug problem, given two jugs of volume jug1 and jug2, where jug1 &lt; jug2, obtain a volume t, where t &lt; jug2.

The algorithm below basically always pours from the smaller jug into the bigger jug, how would you improve the solution ?

I think I get the minimum number of steps this way... am I correct ?

jug1 = 5
jug2 = 7
t = 4

def jugSolver(amt1, amt2):

    print(amt1, amt2)

    if (amt1 == t and amt2 == 0) or (amt1 == 0 and amt2 == t):
        return

    elif amt2 == jug2:
        jugSolver(amt1, 0)

    elif amt1 != 0:
        if amt1 &lt;= jug2-amt2:
            jugSolver(0, amt1+amt2)
        elif amt1 &gt; jug2-amt2:
            jugSolver(amt1-(jug2-amt2),amt2+(jug2-amt2))

    else:
        jugSolver(jug1, amt2)

jugSolver(0,0)
Your code is not a “good” practice at recursion.  Every “recursive” call to jugSolver is the last statement that is executed in the current call, thus the whole function can easily be replaced by a simple loop:

print(amt1, amt2)
while amt1 != t  and  amt2 != t:
    if amt2 = jug2:
        amt2 = 0
    elif amt1 != 0:
        if amt1 &lt;= jug2 - amt2:
            amt1, amt2 = 0, amt1+amt2
        else:
            amt1, amt2 = amt1 - (jug2-amt2), jug2
    else:
        amt1 = jug1
    print(amt1, amt2)


Your assumption that pouring from the smaller jug into the bigger jug always results in the minimum number of steps is flawed.  Consider t=2.  Your way:


5, 0
0, 5
5, 5
3, 7
3, 0
0, 3
5, 3
1, 7
1, 0
0, 1
5, 1
0, 6
5, 6
4, 7
4, 0
0, 4
5, 4
2, 7


Compare with:


0, 7
5, 2


So you’ll need to relook at solving the problem with different possible moves.