Python list index out of range in recursive funciton

Question

I have this homework problem in recursion: checking for valid parentheses. The question asks me to write a function that gets a string and a counter as an input and return whether the parentheses were opened and closed properly.

def is_valid_paren(s, cnt=0):

    lst1 = list(s)

    if lst1 == [] and cnt ==0:
        return True

    if lst1[0] == '(':
        cnt+=1
        return is_valid_paren(lst1[1:], cnt)

    elif lst1[0] == ')':
        cnt-=1
        return is_valid_paren(lst1[1:], cnt)

    else:
        return is_valid_paren(lst1[1:], cnt)

This is my code, however I keep getting a list index out of range error when I try running it on some strings. Any help on why I get this error message would be greatly appreciated, Thanks!

This is unrelated to the main logic error that leads to the exception, but unless you intend a string like "))((" to count as "valid", you probably want to check that cnt is greater than zero in the elif branch, before you recurse. — Blckknght
– Blckknght, Commented Dec 8, 2022 at 5:53

Barmar · Accepted Answer · 2022-12-08 04:48:51Z

3

Did you notice that your function never returns False?

It should return False when lst1 is empty and cnt != 0. You never check for that, so you get an error when you try to use lst1[0] in this case.

def is_valid_paren(s, cnt=0):

    lst1 = list(s)

    if lst1 == []:
        return cnt == 0

    if lst1[0] == '(':
        cnt += 1
    elif lst1[0] == ')':
        cnt -= 1

    return is_valid_paren(lst1[1:], cnt)

answered Dec 8, 2022 at 4:48

Barmar

789k57 gold badges555 silver badges669 bronze badges

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

Collectives™ on Stack Overflow

Python list index out of range in recursive funciton

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related