Recursion Error thrown, but task runs less than 5000 iterations when in a while loop

Question

This is the classic water jug problem[where 2 waterjugs of 7 and 3 lts are given. We have to get 5lts out of it]. I am trying to solve this using random search. 'maximum recursion depth exceeded while calling a Python object' error is thrown when using a function random_search(), but when using a while loop, the task runs under 5000 cases in most cases.

If the loop runs under 5000 iterations in most cases, why is there a recursion error thrown?

Using a Function

# Waterjug Problem
import random
import sys 
sys.setrecursionlimit(5000)

# We have 2 jugs of capacities 7 and 3 Lts respectively, We have to reach the target 5 Lts.
j1, j2, target = 7, 3, 5

# iteration counter
counter = 0

def random_search(amt1, amt2):
    r = random.randint(1,6)

    if amt1 == target:
        amt2 = 0
        return print(f"We have reached the target state {(amt1, amt2)}")
    
    if r==1:
        return random_search(0, amt2)
    elif r==2:
        return random_search(amt1, 0)
    elif r==3:
        return random_search(j1, amt2)
    elif r==4:
        return random_search(amt1, j2)
    elif r==5:
        return random_search(amt1 + min(amt2, (j1-amt1)), amt2 - min(amt2, (j1-amt1)))
    elif r==6:
        return random_search(amt1 - min(amt1, (j2-amt2)), amt2 + min(amt1, (j2-amt2)))

random_search(0, 0)

This throws a Recursion Error: maximum recursion depth exceeded while calling a Python object error.

Using a While Loop

# Using while loop 
import random
j1 = 7
j2 = 3
amt1 = 0
amt2 = 0
counter = 0

while amt1!=5:
r = random.randint(1,6)

if r==1:
amt1 = 0
elif r==2:
amt2 = 0
elif r==3:
amt1 = j1
elif r==4:
amt2 = j2
elif r==5:
amt1 = amt1 + min(amt2, (j1-amt1))
amt2 = amt2 - min(amt2, (j1-amt1))
elif r==6:
amt1 = amt1 - min(amt1, (j2-amt2))
amt2 = amt2 + min(amt1, (j2-amt2))

counter+=1

print(f"The final target is arrived {(amt1,0)} in {counter+1} steps")

This while loop outputs

The final target is arrived (5, 0) in 317 steps
The final target is arrived (5, 0) in 2792 steps
The final target is arrived (5, 0) in 3809 steps
The final target is arrived (5, 0) in 313 steps
The final target is arrived (5, 0) in 379 steps
The final target is arrived (5, 0) in 1991 steps
The final target is arrived (5, 0) in 78 steps
The final target is arrived (5, 0) in 1080 steps
The final target is arrived (5, 0) in 405 steps

score 0 · Answer 1 · answered Mar 29 '23 at 09:38

0

If there are case when the recursion works, without throwing the maximum recursion depth error, then it should come from the recursion limit set in Python. To see that limit:

import sys

print(sys.getrecursionlimit())

On many machines, this is set to 1000 by default.

You can technically change it, but it is often advised not to. (In case you are still interested in modifying it, you should have answers here)

Obviously, if your code always throw the maximum recursion depth error, then there is an error in your code, seeing as there should be some instances where the solution is found in less than 1'000 iterations.

answered Mar 29 '23 at 09:38

GregoirePelegrin

1,206
2
7
23

I set the recursion limit to 10000 but it still throws a **maximum recursion depth**. I used the same logic in the while loop as in the function. I am not able to figure out the error. Can you please take a look at the two blocks and tell if you can state any difference? – Sivashankaran S Mar 29 '23 at 12:12
I haven't been able to find any discrepancies between the sequential and recursive version, but this doesn't ensure there is none. Could you try a couple of times and tell me if any has been successful? If yes, then you may be in the same case as in the sequential, with numbers of iteration sometimes below, sometimes above the threshold. If not, then there either are differencies between your codes, or there is a mechanism which works in the sequential but not in the recursive. Simply to test something, could you include the target as a parameter? `def random_search(amt1, amt2, target):` – GregoirePelegrin Mar 29 '23 at 13:14
1

I don't see the reason why but splitting the final two elif cases in the function straightened it all out. Thankyou so much – Sivashankaran S Mar 29 '23 at 20:51

Recursion Error thrown, but task runs less than 5000 iterations when in a while loop

1 Answers1