在递归调用（列表、集合）之间共享变量

Question

我开始解决一些关于递归的问题，我注意到需要有一个共享变量（例如 set/list）来附加（或在集合的情况下添加）结果到和return。我在网上搜索并找到了一些解决方案，这些解决方案在某些情况下似乎对我有用，但在其他情况下却不起作用 - 我尝试了全局变量、在递归函数之外定义的列表等等。

我无法理解为什么它在某些情况下有效而在其他情况下无效（也许我不知道递归调用是如何工作的？）

# Shared list/set across multiple calls: Works
# Task: Print from n in descending order
s = [] # list defined outside the recursive function
def rec(n):
    if n == 0:
        return s
    else:
        s.append(n)
        rec(n-1)
        return s

print(rec(5))
# prints: [5, 4, 3, 2, 1], as expected.

如果我将共享变量作为函数调用的一部分传递，这也有效：

def rec(n, s=[]):
    if n == 0:
        return s
    else:
        s.append(n)
        rec(n-1, s)
        return s
    
print(rec(5))
# prints: [5, 4, 3, 2, 1], as expected.

接下来，类似地，我在下一个任务中尝试了这个：

# Task: Print permutations of [1, 2, 3]: Doesn't work!
lst = []
def permuteArr(arr, idx=0):
    if idx == len(arr):
        print(arr)
        lst.append(arr)
    
    for i in range(idx, len(arr)):
        arr[i], arr[idx] = arr[idx], arr[i]
        permuteArr(arr, idx+1)
        arr[i], arr[idx] = arr[idx], arr[i]

permuteArr([1, 2, 3])
print(lst) # prints: 
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 2, 1]
# [3, 1, 2]
# [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
# why is the list different from the printed arr values 
# when I have lst defined outside the function?
# Also doesn't work when I pass lst as an argument like earlier.

同样，我正在尝试用 DFS 递归地解决岛屿数量的 leetcode 问题：https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1374/。我用这个视频来了解如何递归地解决这个问题：https://www.youtube.com/watch?v=ZixJexAaOAk 和这里的女士，她用 0 标记访问过的节点（对于水）。如果我尝试像这样维护一个访问集：

from collections import deque
def numIslands(grid):
    """
    :type grid: List[List[str]]
    :rtype: int
    """
    # Approach #4: Using recursive DFS, outside visited.
    # https://www.youtube.com/watch?v=ZixJexAaOAk
    def dfs(grid, r, c):
        # global visited - doesn't work. NameError
        # Passing visited as a variable in this call also fails
        if r<0 or r>=ROWS or c<0 or c>=COLUMNS or (r, c) in visited:
            return
            # Mark this node as water now (visited)
            # Since this is marked as 0 in-place,
            # the outer function won't consider this in the next loop
        if grid[r][c] == "1":
            visited.add((r, c)) # visited set instead of grid[r][c] = 0
            dfs(grid, r+1, c)
            dfs(grid, r, c+1)
            dfs(grid, r-1, c)
            dfs(grid, r, c-1)
        

    output = 0
    ROWS, COLUMNS = len(grid), len(grid[0])
    visited = set()

    for r in range(ROWS):
        for c in range(COLUMNS):
            if grid[r][c] == "1":
                # visit all the neighbours of this "1" and come back
                dfs(grid, r, c)
                output+=1

    return output


numIslands([
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
])

我收到了达到的最大递归深度，因为据我了解，它没有找到访问过的节点，只是一次又一次地递归它们。我尝试将 visited 作为 dfs 函数调用的一部分传递并创建 visited 作为全局变量（收到 NameError 因为函数无法找到 visited），所有这些都不起作用。

如何在这些实例中跨递归调用正确维护共享变量？为什么它对某些情况有效，但对我提到的其他情况无效？

Answer 1

您应该尽可能避免持久状态。你应该特别避免全局持久状态。如果你的递归函数使用全局容器，你将只能调用一次；在那之后，全局容器被第一次调用的数据污染了。

请注意，使用容器作为默认参数实际上与使用全局变量相同，但有一个额外的致命缺陷：与理论上可以重置的真实全局变量不同，没有方便的方法来重置默认参数规范。当你写：

def func(s=[]):
    …

函数定义执行一次。除非您重新定义函数，否则它不会再次执行。当定义被执行时—— 而不是 函数被调用时——默认值被计算并存储在函数的原型中。在上面的例子中，默认值是一个列表，所以它总是同一个列表。这很少是你想要的。

我想您没有注意到第一个函数的问题，因为您只尝试运行该函数一次。一次是不够的测试，永远。（除非你正在构建一个世界末日设备，在这种情况下，一次太多了。老实说，我从来没有想过 Strangelove 博士会 return 相关。）

Python 提供了几种方法来克服这个问题，尽管最好的解决方案几乎总是避免依赖于可变状态。一种可能性是将可变值作为参数传递给递归函数，这实际上只有在编写一个创建可变容器并使用它调用递归函数的包装器时才可行：

def rec_helper(n, s):
    if n:
        s.append(n)
        return rec_helper(n-1, s)
    else:
        return s

def rec(n):
    return rec_helper(s, [])

但更简洁的解决方案通常是使辅助函数成为嵌套函数并对可变状态使用闭包：

def rec(n):
    s= []
    def helper(n):
        if n:
            s.append(n)
            return helper(n-1)
        else:
            return s

    return helper(n)

如上所述，最干净的方法就是避免可变状态：

def rec(n):
    def helper(n, s):
        if n:
            return helper(n-1, s + [n])
        else:
            return s
    return helper(n, [])

Answer 2

我找到了另一种在递归调用中共享变量的方法，很像使用全局变量，但略有不同 - 通过使用 nonlocal 关键字。

# Trying to use a counter across recursion calls
def factorial(x):
    counter = 0 
    def helper(x):
        if x == 0:
            return 1
        counter+=1 # UnboundLocalError
        return x*helper(x-1)
    
    print(counter)
    res = helper(x)
    print(counter)
    return res

并带有 nonlocal 关键字：

def factorial(x):
    counter = 0 
    def helper(x):
        nonlocal counter
        if x == 0:
            return 1
        counter+=1
        return x*helper(x-1)
    
    print(counter)
    res = helper(x)
    print(counter)
    return res

同样，使用 counter = [0] 然后递增 counter[0]+1 也有效，因为列表在多个调用中作为参考进行维护，并且不会创建新副本。因此相同的内存位置用于在所有递归调用中递增。

仅供参考 - 任何关注此内容的人。

在递归调用（列表、集合）之间共享变量

Sharing variables across recursion calls (lists, sets)

python

algorithm

recursion

data-structures