I'm starting to solve some questions on recursion, where I noticed the need of having a shared variable (such as a set/list) to append (or add in case of a set) results to and return. I searched online and found some solutions, which seem to work for me in some cases and not in others - I tried global variables, lists defined outside the recursive functions and so on.
I'm unable to understand why it works in certain cases and doesn't work in others (maybe I'm missing how the recursion calls are working?)
# 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.
This also works if I pass a shared variable as a part of the function call:
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.
Next, similarly, I tried this on the next task:
# 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.
Similarly, I'm trying to solve the leetcode problem of number of Islands: https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1374/ recursively with DFS.
I used this video to understand how to solve this recursively: https://www.youtube.com/watch?v=ZixJexAaOAk and the lady here, she marks the visited nodes with 0 (for water). If I try to maintain a visited set here like so:
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"]
])
I receive a maximum recursion depth reached, because from what I understand, its not finding the visited nodes and just recursing through them again and again. I tried passing visited as a part of the dfs function call and creating visited as a global variable (received NameError as function wasn't able to find visited), all of which don't work.
How to maintain shared variables correctly across recursion calls in these instances? Why does it work for some, but not for the other cases I mentioned?
CodePudding user response：
You should avoid persistent state whenever possible. And you should particularly avoid global persistent state. If your recursive function uses a global container, you will only be able to call it once; after that, the global container is contaminated with data from the first call.
Note that using a container as a default argument is effectively the same as using a global variable, with one additional fatal flaw: unlike real global variables, which could in theory be reset, there is no convenient way to reset a default argument specification. When you write:
def func(s=[]):
…
the function definition is executed once. It's not executed again unless you redefine the function. And when the definition is executed --not ehen the function is called-- the default value is computed and stored in the function's prototype. In the above example, the default value is a list, and so it will always be the same list. That's very rarely what you want.
I suppose you didn't notice that issue with the first function because you only tried running the function once. Once is not enough testing, ever. (Unless you're building a Doomsday device, in which case once is too many. I honestly never thought Dr. Strangelove would return to relevancy.)
Python offers a couple of ways to overcome this problem, although the best solution is almost always to avoid depending on mutable state. One possibility is to pass the mutable value as an argument to the recursive function, which is really only feasible if you write a wrapper which creates the mutable container and calls the recursive function with it:
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, [])
But a cleaner solution is often to make the helper function a nested function and use closures for the mutable state:
def rec(n):
s= []
def helper(n):
if n:
s.append(n)
return helper(n-1)
else:
return s
return helper(n)
Far and away the cleanest, as mentioned above, is to avoid mutable state:
def rec(n):
def helper(n, s):
if n:
return helper(n-1, s [n])
else:
return s
return helper(n, [])