How does this recursive code work?

[member 428835]

Hi PF!

Here is a code that generates $n$ amount of valid combinations of parenthesis e.g. n = 2 implies (()), ()(). But this wouldn't work )()( or this ))((.

def generate(result, s, _open, close, n):
    # Base condition
    if close == n:
        result.append(s)
        return
    # If the number of _open parentheses is less than the given n
    if _open < n:
        generate(result, s + "(", _open + 1, close, n)
    # If we need more close parentheses to balance
    if close < _open:
        generate(result, s + ")", _open, close + 1, n)

def generateParenthesis(n):
    # Resultant list
    result = []
    # Recursively generate parentheses
    generate(result, "", 0, 0, n)
    return result
if __name__ == "__main__":
    n = 2;
    print(generateParenthesis(n))

My issue on understanding it is the function generate. Specifically, when I pass the first $n=0$ case the if statement in line 7 is activated (better word for this?) since _open < n. The variable s is now ( and we are told to plug this back into the generate function. So we do this and again line 7 is activated, so now s is ((. We again plug this back into the generate function only this time line 10 is enabled, changing s to ((), where we go back into the generate function. Lastly, we have (()), again from line 10. This takes care of (()) but what about the ()() solution? How is it being generated? What am I missing?

 

[jedishrfu]

The best explanation is in the example of a factorial as a recursive function:

def fact(int n):
    return n*fact(n-1)

Now you can see it will recursively call fact() forever using n, n-1, n-2 ... but won't ever escape the loop. BAD Function.

You need an escape plan added to it when n==1 or n==0 The zero is better

def fact(int n):
    if n==0 return 1
    return n*fact(n-1)

Lastly, you need a condition for a bad n value ie n<0 to make it more robust

def fact(int n):
    if n<0 return 0
    if n==0 return 1
    return n*fact(n-1)

 

[member 428835]

The best explanation is in the example of a factorial as a recursive function:

def fact(int n):
    return n*fact(n-1)

Now you can see it will recursively call fact() forever using n, n-1, n-2 ... but won't ever escape the loop. BAD Function.

You need an escape plan added to it when n==1 or n==0 The zero is better

def fact(int n):
    if n==0 return 1
    return n*fact(n-1)

Lastly, you need a condition for a bad n value ie n<0 to make it more robust

def fact(int n):
    if n<0 return 0
    if n==0 return 1
    return n*fact(n-1)

Funny enough I actually started by looking at the factorial recursive formula before posting. It makes sense to me. But I still don't see how generate will ever escape line 7 without s = (( for the n = 2 case.

 

[FactChecker]

My issue on understanding it is the function generate. Specifically, when I pass the first $n=0$ case the if statement in line 7 is activated (better word for this?) since _open < n. The variable s is now ( and we are told to plug this back into the generate function. So we do this and again line 7 is activated, so now s is ((.
We again plug this back into the generate function only this time line 10 is enabled, changing s to ((), where we go back into the generate function. Lastly, we have (()), again from line 10. This takes care of (()) but what about the ()() solution? How is it being generated? What am I missing?

I assume that you have run it and that it does, in fact, work. Notice that a call to 'generate" causes it to call itself recursively two times, once to add another open and a second time to add a close (if possible) instead of another open. I think that takes care of both situations. But I can't really convince myself that it works unless you say that you have tested it.

1) I think that the comments could have been better.
2) You might want to step through this in a debugger or add some well-placed prints of the variables to see what is happening.

 

[PeterDonis]

I still don't see how generate will ever escape line 7 without s = (( for the n = 2 case.

What happens when s = (( and the _open < n condition is false, so the function goes on to the next condition, close < _open? More particularly, how many times will generate have to call itself recursively until the close == n if condition is satisfied? And what happens when it returns in the close == n block after appending a string? More particularly, how many recursive calls will end up being exited at that point, and at what line of the generate function will execution be when that is done?

(If you're having trouble imagining the answers to all these questions, a useful and commonly used trick is to insert print statements at key points in the code, that output values of key variables at those points.)

 

[PeterDonis]

I assume that you have run it and that it does, in fact, work.

I've run it and it works, so I assume the OP has as well.

 

[PeterDonis]

I think that takes care of both situations.

It does, but the way it does is not at all obvious if you're not used to analyzing recursive function calls.

 

[member 428835]

What happens when s = (( and the _open < n condition is false, so the function goes on to the next condition, close < _open? More particularly, how many times will generate have to call itself recursively until the close == n if condition is satisfied? And what happens when it returns in the close == n block after appending a string? More particularly, how many recursive calls will end up being exited at that point, and at what line of the generate function will execution be when that is done?

(If you're having trouble imagining the answers to all these questions, a useful and commonly used trick is to insert print statements at key points in the code, that output values of key variables at those points.)

I think my trouble actually stems after the first iteration, where s = (. It's unclear to me how it arrives at the ()() solution.

 

[FactChecker]

I think my trouble actually stems after the first iteration, where s = (. It's unclear to me how it arrives at the ()() solution.

In the "generate" routing, put prints before and after each call to "generate". Make sure that the prints label themselves clearly so you know which printed line comes from which print statement. Run it and see if that helps to clarify it.

 

[PeterDonis]

I think my trouble actually stems after the first iteration, where s = (. It's unclear to me how it arrives at the ()() solution.

In that iteration (where the arguments are s = (, _open = 1, close = 0), the first if condition is true (for _open < n), so the recursive call in that block is made. That call ends up appending the string (()) to the result list (after several more levels of recursive calls).

What happens when that recursive call finally exits and execution returns to the point where it was made? Remember, at this point, we are back in the iteration where the arguments are s = (, _open = 1, close = 0, and we have just returned from the recursive call at line 8. What happens next?

 

[FactChecker]

I think my trouble actually stems after the first iteration, where s = (. It's unclear to me how it arrives at the ()() solution.

It seems clear what must be happening:
Level, line, result:
1 8 (
2 11 ()
3 8 ()(
4 11 ()()

It just remains to clarify the details.
PS. "iteration" is probably the wrong word. Each call to generate adds a level to a tree of possible results.

 

[member 428835]

In that iteration (where the arguments are s = (, _open = 1, close = 0), the first if condition is true (for _open < n), so the recursive call in that block is made. That call ends up appending the string (()) to the result list (after several more levels of recursive calls).

What happens when that recursive call finally exits and execution returns to the point where it was made? Remember, at this point, we are back in the iteration where the arguments are s = (, _open = 1, close = 0, and we have just returned from the recursive call at line 8. What happens next?

Got it. It will then go to the next if statement, triggering the ) to be appended to the s = (, making the first (). Dang that's confusing! But I'm all locked in, thanks everyone!