How does this recursive code work?

  • Python
  • Thread starter member 428835
  • Start date
  • Tags
    Code Work
In summary, the code in the conversation generates a given number of valid combinations of parentheses. It does this through a recursive function called generate, which adds open and close parentheses to a string until the number of opens and closes are equal, creating a valid combination. The code also includes conditions for handling invalid inputs and escaping the recursive loop.
  • #1
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 ))((.

Python:
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?
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
The best explanation is in the example of a factorial as a recursive function:
Code:
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
Code:
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
Code:
def fact(int n):
    if n<0 return 0
    if n==0 return 1
    return n*fact(n-1)
 
  • #3
jedishrfu said:
The best explanation is in the example of a factorial as a recursive function:
Code:
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
Code:
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
Code:
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.
 
  • #4
joshmccraney said:
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.
 
Last edited:
  • Like
Likes member 428835
  • #5
joshmccraney said:
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.)
 
  • Like
Likes FactChecker
  • #6
FactChecker said:
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.
 
  • Like
Likes FactChecker
  • #7
FactChecker said:
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.
 
  • Like
Likes member 428835 and FactChecker
  • #8
PeterDonis said:
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.
 
  • #9
joshmccraney said:
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.
 
  • #10
joshmccraney said:
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?
 
  • Like
Likes member 428835
  • #11
joshmccraney said:
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.
 
  • Like
Likes member 428835
  • #12
PeterDonis said:
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!
 

FAQ: How does this recursive code work?

1. How does recursion work?

Recursion is a programming technique where a function calls itself repeatedly until a certain condition is met. This allows for solving complex problems by breaking them down into smaller, simpler subproblems.

2. What is the base case in recursive code?

The base case is the condition that stops the recursive function from calling itself. It is the simplest version of the problem that does not require any more recursive calls.

3. How do you avoid infinite recursion?

To avoid infinite recursion, the recursive function must have a base case that will eventually be met. Additionally, the input parameters of the function should be modified with each recursive call to bring it closer to the base case.

4. Can any problem be solved using recursion?

No, not every problem can be solved using recursion. Some problems may be better solved using iterative methods. It is important to understand the problem and the limitations of recursion before implementing it.

5. How do you determine the time complexity of recursive code?

The time complexity of recursive code can be determined by analyzing the number of recursive calls and the complexity of each call. The time complexity can usually be expressed in terms of the input size and the number of recursive calls made.

Similar threads

Replies
4
Views
3K
Replies
9
Views
2K
Replies
5
Views
2K
Replies
15
Views
2K
Replies
29
Views
2K
Replies
2
Views
973
Replies
8
Views
1K
Replies
1
Views
1K
Replies
10
Views
1K
Back
Top