How can I fix this maximum recursion depth error?

Question

I am trying to implement a binary search to guess a number between 0 and 255 (both inclusive). My guess would be analyzed by a liar function which returns 1 if the key to find is greater than my guess, -1 if the key is less than my guess and 0 if I guessed the right number. However the liar function can lie up to 8 times.

Now the game is controlled by a bigger program (see this repo) which terminates the game as soon as the liar returns 0, so in writing my binary search I don't need to account for an end condition, I just keep guessing till the liar runs out of lies and finally return 0 making the game runner stop everything.

This is my binary search:

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    low = high = guess = res = 0
    
    def makeAguess(counter):
        nonlocal low, high, guess, res
        if (counter % 8) == 0:
            low = 0
            high = 255
            counter = 0
        guess = (low + high) // 2
        res = liar( guess );
        if res > 0:
            low = guess + 1
        else:
            high = guess - 1
        makeAguess( counter + 1 )

    makeAguess( 0 )

A binary search over 256 values is granted to find the key in 8 turns, but since the liar can lie 8 times I need to run at most 9 searches to find the key, so the game should end after at most 8 * 9 = 72 guesses.

However I keep getting:

RecursionError error: maximum recursion depth exceeded in comparison

And if I swap the 8 in if (counter % 8) == 0: with a 9 I get a reasonable:

guessed invalid value: -1

The algorithm seems correct and since that's my very first Python code, I think there is something wrong in how I am using the language.

Anyone can spot the bug?

EDIT:
You can run the game by doing

git clone https://github.com/Artemis21/guessers-and-liars

cd guessers-and-liars/guessers

nano Create theGuesser.py

then pasting my code into the nano editor and saving the file.

Finally run

python main.py -r 1

from the guessers-and-liars directory and wait for the response.

Answer 1

I see you like to play with danger.

The fix is to add a return statement to your recursive function.

You are relying on another thread to (unceremoniously) terminate this Main thread before this Main thread can exceed your stack frame limit. Always be very, very careful with recursive functions that you know precisely when it recurses (deeper) or returns (shallower).

---

From the link:

If you return 0 when the guess is not equal to your number, your opponent will win anyway

Liar will never falsely give you 0 if you guessed incorrectly. Thus, conversely, if liar returns 0 then we know we guessed correctly.

How does this help us? It means that if the liar lied even once during that guess round, our binary search will go out of bounds because we are now searching in a sub-range that does not contain the target.

You can see this from the output of my sample code below (which either converges on the correct number, or returns -1)

---

I heard you like iterative solutions:

from random import randint
from typing import Callable

def guessNumber(liar: Callable[[int], int]) -> int:
    l, r = 0, 255
    while l <= r:
        m = (l + r) // 2
        guess = liar(m)
        if guess == -1:
            l = m + 1
        elif guess == 1:
            r = m - 1
        else:
            return m
    return -1

def liar(guess: int, liesLeft: int = 8, answer: int = randint(1, 256)) -> bool:
    if guess > answer:
        result = 1
    elif guess < answer:
        result = -1
    else:
        return 0
    if liesLeft and randint(0, 8) == 0:  # 1 in 8 chance of lying
        liesLeft -= 1
        result = -result
    return result

for i in range(10):
    print(f'attempt #{i}: {guessNumber(liar)}')

Output:

attempt #0: -1
attempt #1: 212
attempt #2: -1
attempt #3: 212
attempt #4: -1
attempt #5: -1
attempt #6: -1
attempt #7: 212
attempt #8: 212
attempt #9: 212

---

I heard you like recursive solutions. One-liner change:

def guessNumber(liar: Callable[[int], int]) -> int:
    l, r = 0, 255
    while l <= r:
        m = (l + r) // 2
        guess = liar(m)
        if guess == -1:
            l = m + 1
        elif guess == 1:
            r = m - 1
        else:
            return m
    return guessNumber(liar)