Seemingly straightforward recursive function ends in infinite loop

Question

I have written the following code:

def incr_num(x, y):
    while x <= y:
        print x
        incr_num(x+1, y)

When I invoke this as

incr_num(1, 10)

it gets into an infinite loop and gives this output:

1
2
3
4
5
6
7
8
9
10
10
10
10
10
10
10

(number 10 keeps repeating)

I was expecting it to print numbers 1-10. I am not able to understand why it doesn't. Can someone please tell me why this happens.

I'm using python2.7.

Answer 1

The correct version would be:

def incr_num(x, y):
    if x <= y:
        print x
        incr_num(x+1, y)

Note that x is printed at most once for each recursive function call.

UPDATE: The reason your function doesn't work is that incr_num(10,10) prints 10 and then calls incr_num(11,10), which immediately returns. After this, incr_num(10,10) continues. It does not break out of the while loop and continues through with the next iteration, printing 10 and calling incr_num(11,10) again. As you can see, this cycle does not end.

Answer 2

If your loop executes forever, it must mean the condition x <= y is always True. Consider this:

while x <= y:
    print x

It's a simplified version of your code, but that is essentially what you're doing.

Try:

def incr_num(x, y):
    if x <= y:
        print x
        incr_num(x+1, y)

This prints the numbers 1 through 10.

Answer 3

incr_num(x+1, y) keeps getting called until x == y, and then the recursion ends, then you return to the previous execution where x=9, so x still has the value it's passed, and x <= y is not False. Therefore the recursion happens again and prints 10

You'll at least want a x+=1 after that recursive call.

I wouldn't call a while loop inside recursion straightforward ;) If that's your base case for ending the recursion, you want if x<=y

Answer 4

Your condition should be a if condition instead of a while loop because you are not changing the value of x within the while loop and Everytime the condition becomes true and makes a recursive call.

Here is a corrected version of it

def incr_num(x, y):
        if x <= y:
            print x
            incr_num(x+1, y)