# How can a global variable go back to an un-updated state?

I am doing a leetcode question using backtracking: https://leetcode.com/contest/weekly-contest-212/problems/path-with-minimum-effort/ and found output I can’t explain. Maybe there’s something lacking with my understanding of global variables when used with recursion?

My reproducible solution (Time Limit Exceeded, but that’s a separate discussion if you want to start) :

``````import numpy as np
import math

min_effort = math.inf

def valid(r,c,visited):
return r < visited.shape[0] and r >= 0 and c < visited.shape[1] and c >= 0 and visited[r,c] == 0

def find_path(heights_arr,visited,r,c,effort,max_row, max_col):
global min_effort

if r == max_row and c == max_col:
print(f'-------------------Found end: effort is {effort}')
return effort

for row,col in ((r+1,c),(r,c+1),(r-1,c),(r,c-1)):
if valid(row,col,visited):
print(f'going from {r},{c} to {row},{col}')
print(f'effort before recurse: {effort}')
visited[row,col] = 1
updated_effort = max(effort, abs(heights_arr[row,col]-heights_arr[r,c]))  # possibly update current max effort along path
#recursion_res = find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col)
#print(f'min_effort:{min_effort} recursion_res:{recursion_res}')
#min_effort = min(min_effort,recursion_res)

min_effort = min(min_effort,find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col))   # problem
#min_effort = min(find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col),min_effort)

visited[row,col] = 0

print(f'global min_effort after recurse: {min_effort}')

return math.inf
#return min_effort

def minimumEffortPath(heights):
heights_arr = np.array(heights)
rows, cols = heights_arr.shape
max_row, max_col = rows-1, cols-1

r,c = 0,0
visited = np.zeros((rows, cols))
visited[r,c]=1

effort = 0
find_path(heights_arr,visited,r,c,effort,max_row, max_col)

#heights = [[1,2,2],[3,8,2],[5,3,5]]
heights = [[1,2,3],[3,8,4],[5,3,5]]
minimumEffortPath(heights)
print(min_effort)
``````

The strange phenomena happens when the destination is reached through path of 1,3,5,3,8,2,3,4,5, after backtracking 5 steps, the global variable went back from 2 to `inf` (with a wrong `inf` as final answer).

How can this happen? Shouldn’t the global variable `min_effort` be capped at 2 throughout the rest of the program run?

This problem can be resolved if the commented code is used instead, to run the `find_path` recursion first and save into `recursion_res` before `min()` comparison rather than directly using the recursion call in min().

It will also be resolved if the order of arguments in min() is switched (i see this as the most important thing to sort out).

It will also be fixed if i replace `return math.inf` with `return min_effort`. Also, totally avoiding global variables and passing `min_effort` along the function parameters and return statements fixes this, but I still want to understand why this is happening.

Below is the proper output, with the correct final answer.

I suspect this has something to do with local scopes I’m not aware of yet.

Edit

I thought through it and understand now. Python evaluates left to right. By doing `min(min_effort,recurse())`, the value of `min_effort` was already evaluated and saved in the local stack of that level of call before the recursion had a chance to update the global `min_effort` to a smaller value than `inf`. Extracting the recursion out and assigning to a var before doing `min()` allows the recursion to run first to update the global before `min()` operation.

The pattern of 2,2,2,2,2,inf,inf appeared because moving backwards from the destination through the numbers 5,4,3,2,8,3,5,3,1, at the scope of 6th and 7th number 3 and 5, `min_effort` had not seen the destination yet and was `inf`, so min() was comparing the initialized `inf` with the returned `math.inf`.

The 1st five 2s were not inf because according to my defined recursion order of down,right,up,left, the recursions seeing 5,4,3,2,8 and already had `min_effort` updated to 2 from the 1st successful path of 1,3,5,3,5. So the 1st give 2s were printing `min(2, recurse())`.

Replacing `return math.inf` with `return min_effort` gives correct result while allowing `min(min_effort,recurse())` because the return gives back the updated global, so even if the 1st argument `min_effort` was evaluated before recursion had a chance to update, the 2nd argument recursing would have returned the updated global to give correct `min()`. `return min_effort` is compulsary when not using globals so the most updated value always is passed back for future loop iterations (directions) to compare. This is not compulsary and `return math.inf` can be used if globals are used with running recursion before `min()` described above to avoid the “un-updated `min_effort` problem” and let the recursion do it’s magic first before `min()`, making the return value of `math.inf` or `min_effort` not important because the caller will handle both return values and give correct min().

This was a good lesson in being really careful with globals. I still can’t debug why Leetcode doesn’t like globals. Something is not being refreshed across test case runs so giving wrong answer, but running the wrong test case as custom input alone gives correct answer.

Summary

Global variable pros:

1. Convenient coding
2. Less parameter passing and simpler recursive functions
3. More immediate value updating and lax return value allowed

Global variable cons:

1. Don’t gel with online coding platforms (risky for job interview automated coding assessments)

Local parameter passing pros:

1. Easier debugging/tracing focusing on local problem space
2. Less side effect

Local parameter passing cons:

1. More verbose function signature

Any opinions on moving `def find_path` into `def minimumEffortPath` and using `nonlocal`? I didn’t do that because following the zen of python: flat better than nested.

1 Like