Gotcha! when using global variable with recursion | by Han Qi | Oct, 2020

[ad_1]

Han Qi
Photo by Andrea Ferrario on Unsplash

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

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

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.

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

Two modifications:
1. Add the beforehand global variable to recursive operate signature find_path(...,min_effort)

2. Return min_effort reasonably than math.inf

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

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
  1. Lax return values allowed ( math.inf or min_effort )
  2. Convenient coding (much less parameter passing and less complicated recursive features)

Global cons:

  1. Don’t gel with on-line coding platforms (dangerous for job interview automated coding assessments)
  2. Constantly have to pay attention to negative effects and variables not inside present stack
  3. Sensitive to operate argument ordering (the foundation of all these troubles)

Local professionals:

  1. Easier debugging/tracing specializing in native downside house
  2. Less negative effects

Local cons:

  1. More verbose operate signature (extra gadgets to trace means longer signature)
  2. Lose capability to return math.inf , should return min_effort to propagate up to date outcomes again to remainder of program

[ad_2]

Source hyperlink

Write a comment