递归的按值传递？-解网

问：

我正在尝试“按值”传递参数。我尝试对递归传递的参数进行深度复制，以防止任何更改循环回父函数调用。

下面是一个代码片段，它试图生成所有可能的括号的数组。

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

不幸的是，调用返回而不是.generateParenthesis(1)['()','()(', '()()']['()']

python-3.x 递归传递值

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))

经过 3 个小时的简化想法，我得到了这个工作代码。

现在它找到了类似 for 的东西，例如。(()())()generateParenthesis(4)

代码非常不言自明。您保留打开/关闭括号的计数，并且仅在有相应的打开时才保留关闭括号。

我选择不使用堆栈，因为 Python 中的所有内容都是通过“指针复制”传递的，因此堆栈（即 OP 中的列表）需要在函数体中创建一个成本高昂的函数体，从而创建列表的本地副本。list(stack)

请注意，我创建了新的字符串（例如），这些新的字符串对象通过“指针复制”传递给递归调用。partial + '('

（对不起，我现在缺少更好的术语。但这很重要）

编辑

您的解决方案存在变量的问题。它的值正在泄漏到第二个递归函数中。此外，您需要了解，除了堆栈之外，不需要所有值复制。newPerm

了解如何简化您的函数。我认为它正在起作用：

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

0赞 DFeng 5/15/2022 #2

使用运算符添加到列表而不是行为，以最好地模拟按值传递行为。+.append()

Python 正式遵守 pass-by-object-reference。在您的情况下，当列表或在子函数中传递和修改时，父函数将看到更新的变量。stackpermstackperm

上一个：为什么 Python Dictionary 的行为类似于对象引用？[复制]

下一个：Python 函数的模板，该函数创建了输入的修改版本，但不修改输入

递归的按值传递？

Pass by value for recursion?

评论