Issue with tracing down the array in Java recursion function

Question

I have an issue with recursion in Java. The question is as such:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

The code for the above problem is recursive and is as mentioned below:

public List<String> generateParenthesis(int n) {
    ArrayList<String> result = new ArrayList<String>();
    dfs(result, "", n, n);
    return result;
}

public void dfs(ArrayList<String> result, String s, int left, int right){
    if(left > right)
        return;

    if(left==0&&right==0){
        result.add(s);
        return;
    }

    if(left>0){
        dfs(result, s+"(", left-1, right);
    }

    if(right>0){
        dfs(result, s+")", left, right-1);
    }
}

I have been able to trace the program upto a particular point, but I am unable to trace it down totally.

if n=2

left=2;right=2;
result="(())", 
__________
| s=""   |
| l=2    |
| r=2    |
|        |
|        |
|________|
    |
    V
__________  
| s=(    |
| l 1    |
| r 2    |
|        |
|        |
|________|
    |
    V
__________
| s=((   |
| l 0    |
| r 2    |
|        |
|        |
|________|
    |
    V
__________
| s=(()  |
| l 0    |
| r 1    |
|        |
|        |
|________|
    |
    V
__________  
| s= (())|
| l=0    |
| r=0    |
|        |
|        |
|________|

how would the program work after what I have mentioned above? Can someone help me tracing it? Thanks.

I don't understand what you mean by "tracing" -- "Can someone help me tracing it?", "able to trace the program" etc. Trace/Tracing is usually used to mean debugging, and you don't seem to be talking about debugging. — Stephen P
– Stephen P, Commented Mar 28, 2017 at 20:01
Good question..i'm learning recursion at this point in time..and had similar doubts even while solving other problems. Thought it would be a good idea to know what's happening here. Thanks — naveen reddy bathu
– naveen reddy bathu, Commented Mar 28, 2017 at 20:02
I think you can solve this problem really easily without using recursion. — Gooz
– Gooz, Commented Mar 28, 2017 at 20:07
Gooz, the issue is not with trying to solve the problem with/without using recursion..I am trying to understand how recursion works. This is just an example that I am using. Any help would be appreciated. Thanks — naveen reddy bathu
– naveen reddy bathu, Commented Mar 28, 2017 at 20:08

DeepFriedPotater · Accepted Answer · 2017-03-28 20:43:29Z

1

From where you left off:

__________
| s=(    |
| l=1    |
| r=2    |
|        |
|        |
|________|
    |
    V
__________  
| s=()   |
| l 1    |
| r 1    |
|        |
|        |
|________|
    |
    V
__________
| s=()(  |
| l 0    |
| r 1    |
|        |
|        |
|________|
    |
    V
__________
| s=()() |
| l 0    |
| r 0    |
|        |
|        |
|________|

If you're using eclipse or any other IDE, it should be easy to set a breakpoint and go through how your program runs line by line (showing all your variables and how they change). If you haven't learned debugging yet, I would encourage you to google it and learn how to debug programs.

What your program is actually doing:

left (l=1, r=2)
  left (l=0, r=2)
    right (l=0, r=1)
      right (l=0, r=0)
        add result to s (l=0, r=0)
    *here you break out of 3 recursive functions and values of l,r reset to (l=1, r=2)*
  right (l=1, r=1)
    left (l=0, r=1)
      right (l=0, r=0)
      add result to s (l=0, r=0)

edited Mar 28, 2017 at 20:43

answered Mar 28, 2017 at 20:27

DeepFriedPotater

462 bronze badges

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

2 Comments

DeepFriedPotater Over a year ago

I can't comment on your post because I am a new user here: The reason why this calls right instead of left is because when you break out of the previous recursive call, you have already called left in the that recursive call so it will go (right -> left -> right) instead of (left -> right -> right)

naveen reddy bathu Over a year ago

Fantastic...thanks a lot for your explanation. Appreciate it.

Collectives™ on Stack Overflow

Issue with tracing down the array in Java recursion function

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related