recursive function going into infinite loop despite condition check

Question

I have a list

s = ["h", "e", "l", "l", "o"]

I try to reverse in place using a recursive function

def reverse_string4(arr, start=0):
    while start < len(arr):
        arr.insert(start, arr.pop())
        reverse_string4(arr, start + 1)

the above goes into an infinite loop, but this one below works

def reverse_string2(arr, start=0):
    if start == len(arr)-1:
        pass
    else:
        arr.insert(start, arr.pop())
        reverse_string2(arr, start + 1)

I am confused when debug start variable increases, then why is not terminating while loop?

The while is an infinite loop. There's nothing in the body of the loop that would make the while condition false. Why do you think you need a while loop and recursion? — khelwood
– khelwood, Commented Apr 26, 2021 at 9:39
then when start becomes 5 why is not terminating the while loop? — tetris555
– tetris555, Commented Apr 26, 2021 at 9:40
Use if instead of while loop because there is no need of while looping in recursion. if start < len(arr): will also work. — Zalak Bhalani
– Zalak Bhalani, Commented Apr 26, 2021 at 9:55
start does not become 5. When you recursively call reverse_string2 you create a new run of the function with its own variables and its own start. But in the original run, the start variable that the while-loop is looking at still has the same value, so it still loops. — khelwood
– khelwood, Commented Apr 26, 2021 at 9:57

tripleee · Accepted Answer · 2021-04-26 10:01:35Z

1

You can easily see what's happening by adding print() statements.

def reverse_string4(arr, start=0):
    print('-> arr %s, start=%i' % (arr, start))
    while start < len(arr):
        print('start %i < len(arr) %i' % (start, len(arr)))
        arr.insert(start, arr.pop())
        print('call reverse_string()')
        reverse_string4(arr, start + 1)
        print('back from call')

Run it with reverse_string4(['h', 'e', 'l', 'l', 'o']):

-> arr ['h', 'e', 'l', 'l', 'o'], start=0
start 0 < len(arr) 5
call reverse_string()
-> arr ['o', 'h', 'e', 'l', 'l'], start=1
start 1 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'h', 'e', 'l'], start=2
start 2 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'h', 'e'], start=3
start 3 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'e', 'h'], start=4
start 4 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'e', 'h'], start=5
back from call
start 4 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'e', 'h'], start=5
back from call
start 4 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'e', 'h'], start=5
back from call
start 4 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'e', 'h'], start=5
back from call
start 4 < len(arr) 5
call reverse_string()
-> arr ['o', 'l', 'l', 'e', 'h'], start=5
back from call
start 4 < len(arr) 5
call reverse_string()

See? The while condition is still true, so it stays in the while loop.

The proper fix is to use either a while loop or recursion (and then, probably return the value called by the recursive call).

answered Apr 26, 2021 at 10:01

tripleee

192k37 gold badges318 silver badges367 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

tetris555 Over a year ago

Thanks, I notice in debug window that once the start becomes 5, it goes back to 4 and that goes infinite. Then do you mean that while and recursive call should not be used together? This is how I understand it.

tripleee Over a year ago

That's basically the gist of this, yes. It's not impossible to combine the two but if you are only just learning, probably don't even try. The standard logic is simply if (something): return recursive_call(): else: return base case and the recursion is what takes care of any (implicit) looping.

tetris555 Over a year ago

Thank you, yes I am learning and practise various exersises.

Collectives™ on Stack Overflow

recursive function going into infinite loop despite condition check

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related