Gotcha! when using global variable with recursion | by Han Qi | Oct, 2020
I used to be engaged on this leetcode query https://leetcode.com/contest/weekly-contest-212/issues/path-with-minimum-effort/ using backtracking and spent a while debugging unusual output. This article discusses some pitfalls when using recursion with global variables, learn how to deal with them, and learn how to change the code from global to native.
Disclaimer: Backtracking solely passing 15/75 take a look at circumstances and Time Limit Exceeded for the remaining, the aim of this text is to spotlight doable points with global variables reasonably than give one of the best options. For extra stunning options using Binary Search, Dijkstra and Kruskal, watch Alex’s walkthrough (starting 7:26) at https://www.youtube.com/watch?v=AM__3Zx1XNw&t=2325s&ab_channel=AlexWice
The problem is to seek out the trail with minimal effort after strolling from high left to backside proper with every step permitting Four instructions of up, down, left, proper.
effort is outlined as the utmost absolute distinction in values between any 2 consecutive squares.
Notebook containing implementation with global vs no global variable: https://gist.github.com/gitgithan/a818d336c2309852a21d99efd619238d
My backtracking answer was to make use of a
visited 2D array to trace visits.
Starting from the top-left cell, we attempt to transfer within the order of down, proper, up, left (this order reaches the vacation spot quicker than another orders, so the global min may be up to date earlier, and used to certain/velocity up the exploration of future paths) if inside rectangle bounds and never visited earlier than. Before transferring (recursing), the go to is marked so future makes an attempt to go to will return False for
Along the best way, the hassle (intialized to 0) of the trail is up to date using abs distinction between the cell we’re going to go to and present cell. If we attain base case (bottom-right cell), return the hassle.
Once a single route of recursion is full, we replace the global minimal
min_effort (initialized to
math.inf) and unmark the cell in that route.
Once all Four instructions from the present cell is completed, we return
math.inf again up the decision stack so it doesn’t wrongly affect the min() of the caller.
This output of 5 2, adopted by two inf was mindboggling. It appeared just like the global variable
min_effort which was up to date from inf to 2 after the primary answer (1, down to three, down to five, proper to three, proper to five) went again to inf! The ultimate reply was additionally wrongly inf as an alternative of 1 (path of 1, 2, 3, 4, 5).
Those 5 2 correspond to the algorithm backtracking from vacation spot 5 to 4,3,2,8,3,5 as a result of all these have all Four instructions both visited or out of bounds, so the following path to strive is to go proper from 1,Zero to 1,1 (Three to eight).
The downside is with the road
min_effort = min(min_effort,find_path(...))
Because python evaluates arguments from left to proper, the global variable
min_effort was already evaluated earlier than coming into the recursion, so no matter occurs within the recursion (together with updates to global variable) has no impact on
At the scope of the three in backside center of the grid, the algorithm has not but discovered a profitable path (the first path being 1,3,5,3,5), so
min_effort was nonetheless
math.inf at that second, and
min(math.inf,math.inf) turned inf.
- Swap arguments
A repair is to easily swap the order of arguments to
min_effort = min(find_path(...), min_effort). This provides the recursion an opportunity to replace the global variable first earlier than comparability.
2. Save into variable first
If you continue to wished to take care of the previous order as a matter of desire, the recursion may be calculated and saved right into a variable first.
recursion_res = find_path(...)
min_effort = min(min_effort, recursion_res)
3. Remove global variables utterly
This was prompted by Leetcode giving mistaken take a look at outcomes working all take a look at circumstances, however working the failing case individually as customized enter provides the proper end result. (can somebody clarify how Leetcode’s checks behave with globals?)
1. Add the beforehand global variable to recursive operate signature
min_effort reasonably than
This will make sure the minimal effort path is at all times propagated by way of the recursive calls. If you ask why not return
min_effort whereas using global variable, that’s workable too, however pointless, since in the event you keep away from the gotcha talked about above,
min_effort would have been up to date to a non-inf worth earlier than the
min(min_effort,find_path(...))comparability, so even when the 2nd argument returns math.inf, the first argument will at all times be up to date to the proper worth as soon as any path first reaches the vacation spot. Also,
math.inf felt extra consultant of a “no solution/bad value”.
However, the argument in help of
return min_effort reasonably than
return math.inf is that it extra precisely represents probably the most up to date program state. Also, we will completely keep away from the gotcha dealing with (the first two fixes described) and use
min(min_effort,find_path(...)) immediately as a result of with
return min_effort the 2nd argument will at all times be up to date, so a “pre-recursion evaluated”
min_effort that might include its initialized
math.inf within the 1st argument causes no hurt. (precisely reverse state of affairs of the earlier paragraph).
Since we’re on the lookout for the global minimal, any path may be influenced by the outcomes of every other path. This affords an opportunity for the present greatest end result to short-circuit future paths as soon as they’re discovered to have longer effort than the present
min_effort . This may be achieved by wrapping the backtracking part (go to,recurse,unvisit) with an additional verify
if updated_effort < min_effort: to largely cut back exploration steps, using “less than” as a result of there isn’t a level making an attempt one thing that gained’t cut back the present greatest.
if updated_effort < min_effort:
visited[row,col] = 1
min_effort = min(min_effort,find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col))
visited[row,col] = 0
- Lax return values allowed (
- Convenient coding (much less parameter passing and less complicated recursive features)
- Don’t gel with on-line coding platforms (dangerous for job interview automated coding assessments)
- Constantly have to pay attention to negative effects and variables not inside present stack
- Sensitive to operate argument ordering (the foundation of all these troubles)
- Easier debugging/tracing specializing in native downside house
- Less negative effects
- More verbose operate signature (extra gadgets to trace means longer signature)
- Lose capability to return
math.inf, should return
min_effortto propagate up to date outcomes again to remainder of program
When using globals, if I had returned
min_effort or coded correctly using repair 2 above initially, I might not have seen this gotcha in any respect. It’s a blessing in disguise that returning probably the most intuitively right worth and being lazy with (probably) extraneous variable assignments allowed me to strengthen my understanding of python analysis order and debugging expertise.