Pass by value for recursion?

Question

I am trying to pass a parameter "by value". I have tried making a deep copy of the parameter that is passed recursively in order to prevent any changes from circling back to the parent function calls.

Here is a snippet of code that tries to generate the array of all possible parentheses.

def generateParenthesis(n):
    #Iterate for each move.
    M = 2 * n
    retArray = []
    def recHelper(numMoves, perm, stack):
        print("Function call: ", numMoves, perm, stack)
        newPerm = copy.deepcopy(perm)
        newStack = stack.copy()
        #Base case, no moves
        if (numMoves == 0):
            retArray.append(newPerm)
            return

        #Case when left move is valid
        if (numMoves != len(newStack)):
            #Apply the left move. Pass it recursively
            newPerm +='('
            #Update the stack accordingly
            newStack.append('(')
            #Decrease numMoves
            newNumMoves = numMoves - 1
            #Call it recursively
            recHelper(newNumMoves, newPerm, newStack)
        #Case when right move is valid
        if len(newStack) != 0:
            #Apply the right move. Pass it recursively
            newPerm +=')'
            #Update the stack accordingly, delete the top, last elm
            newStack.pop()
            #Decrease numMoves
            newNumMoves = numMoves - 1
            #Call it recursively
            recHelper(newNumMoves, newPerm, newStack)
        #done
        return
    recHelper(M, "", [])
    return retArray

Unfortunately, calling generateParenthesis(1) returns ['()','()(', '()()'] and not ['()'].

Answer 1

def generateParenthesis(n):
    retArray = []

    def append_solutions(partial, opened_p, closed_p):
        if opened_p < n:
            append_solutions(partial + '(', opened_p + 1, closed_p)
        if closed_p < n and opened_p > closed_p:
            append_solutions(partial + ')', opened_p, closed_p + 1)

        if opened_p == closed_p == n and partial:
            retArray.append(partial)

    append_solutions('', 0, 0)
    return retArray

print(generateParenthesis(1))
print(generateParenthesis(2))
print(generateParenthesis(3))
print(generateParenthesis(4))
print(generateParenthesis(5))

After 3 hours of simplifying ideas, I came with this working code.

Now it finds things like (()())() for generateParenthesis(4), for instance.

The code is very self explanatory. You keep a count of opened/closed parenthesis and only close parenthesis when there are correspondent opened.

I chose not to use a stack because since everything in Python is passed by "pointer copy", stacks (i.e. lists in your OP) would require a costly list(stack) in the function body, creating a local copy of the list.

Notice that I create new strings (partial + '(', for instance), and these new string objects are passed by "pointer copy" to recursion calls.

(Sorry I lack a better term now. But this is important)

---

Edit

Your solution has a problem with the variable newPerm. Its value is leaking into the second recursive function. Also, you need to understand that all your copying of values is not needed except for the stack.

See how your function can be simplified. I think it's working:

def generateParenthesisOP(n):
    #Iterate for each move.
    M = 2 * n
    retArray = []
    def recHelper(numMoves, perm, stack):
        print("Function call: ", numMoves, perm, stack)
        if numMoves == 0:
            retArray.append(perm)
            return

        if numMoves != len(stack):
            left_stack = list(stack)
            left_stack.append('(')
            recHelper(numMoves - 1, perm + '(', left_stack)
        if len(stack) != 0:
            right_stack = list(stack)
            right_stack.pop()
            recHelper(numMoves - 1, perm + ')', right_stack)
    recHelper(M, "", [])
    return retArray