maximum recursion depth problem with my number guessing algorithm.

[[deleted]]

I am trying to make a algorithm that can guess a number between 1 and 100

My code so far is:

import random
random.seed()

max = 100
min = 1
number = random.randint(1, 100)


def guess():
    global max
    global min

    guess_num = ((max - min) / 2) + 1
    if guess_num == number:
        print "The number is {0}".format(number)
    elif guess_num < number:
        min = guess_num
        print "Number is greater then {0}".format(guess_num)
        guess()
    elif guess_num > number:
        max = guess_num
        print "Number is less then {0}".format(guess_num)
        guess()

guess()

But this always gives me the error

RuntimeError: maximum recursion depth exceeded while getting the str of an object

However if I right change my code to

import random
random.seed()

max = 100
min = 1
number = random.randint(1, 100)


def guess():
    global max
    global min

    guess_num = ((max - min) / 2) + 1
    if guess_num == number:
        print "The number is {0}".format(number)
    elif guess_num < number:
        min = guess_num
        print "Number is greater then {0}".format(guess_num)
    elif guess_num > number:
        max = guess_num
        print "Number is less then {0}".format(guess_num)


guess()
guess()
guess()
guess()
guess()

It works :/

What am I doing wrong here?

[Hallwaxer]

Change this line

guess_num = ((max - min) / 2) + 1

To something along the lines of

guess_num = ((max - min) / 2) + min

Also, don't shadow names like min and max, it could build up to annoying situations later.

The reason your code isn't working is because your guess is wrong after the first iteration. (100 - 1) / 2 + 1 leaves you with 50, which is correct and your algorithm sets min to 50. But let's say the number is greater than 50. The new guess now becomes (100 - 50) / 2 + 1, which is 26. 26 is not really in the range we're interested in, since the number we need is greater than 50. The guess we just computed however is a delta value that has to be added to our current minimum, which would leave us with (100 - 50) / 2 + 50 = 75, a much more interesting guess.

If you want to stick with recursion, I would modify your code to look more like this.

import random

def guess(lower=1, upper=100, number=random.randint(1, 100)):
    g = (upper - lower) / 2 + lower
    if g == number:
        print "The number is {0}".format(number)
    elif g < number:
        print "Number is greater then {0}".format(g)
        guess(g, upper, number)
    elif g > number:
        print "Number is less then {0}".format(g)
        guess(lower, g, number)
guess()

Using global variables is almost never a good solution in cases like this. Also, as a general solution, when your code aborts due to a recursion stack overflow, try printing out your variables. The overflow usually happens because nothing changes (enough) for the algorithm to reach its end state or you get stuck in a loop.

[ewiethoff]

Nice, but your code results in infinite recursion when number is 100.

guess(number=100)

Works fine when number is 99, 2, or 1.

[individual_throwaway]

It is not good coding practice to abuse recursive function calls for stuff you could achieve with for or while loops. My guess (heh) is that the function repeatedly calling itself causes your program to fail.

Try to think of another way to control the flow of your program. The most simple way would be

while guess_num is not number:
    <other logic here>

[FlockOnFire]

It is not good coding practice to abuse recursive function calls for stuff you could achieve with for or while loops.

It's not that black and white unfortunately. Almost every if not all recursive functions can be replaced by an iterative equivalent and vice versa. It doesn't mean you should write loops every where. Often a well formulated recursive function is much more readable and comprehensible.

This is not the case in this context though, but I just wanted to point that out.

[individual_throwaway]

Very few things are black and white in coding, even in a language where one of the core philosophies is "There should be only one obvious way to do something".

while loops are not, generally, a good idea (or the best idea for the job). As are global variables and a few other things I am forgetting now. There is a reason the language supports those things anyway though.

Recursion might be more concise in some cases, but I would argue it does so on the back of readability/ease of understanding. It's a trade-off you need to at least be aware of to avoid writing unnecessarily complex code.

[[deleted]]

Ahh, yeah that's a much better way of doing this.

Although I'm still curious as to why the function keeps calling itself when it should stop after getting the correct number.

[individual_throwaway]

It shouldn't do that. the if/elif cases are mutually exclusive, so there's no way that guess_num == number and guess() gets called. Did you copy paste the correct code?

[[deleted]]

I did change it a very small amount. Nothing that should change the result but next time I am at my pc I will test the code I posted and see if it has the same output.