The world’s leading publication for data science, AI, and ML professionals.

Gotcha! when using global variable with recursion

I was working on this leetcode question https://leetcode.com/contest/weekly-contest-212/problems/path-with-minimum-effort/ using…

Be careful with argument order and return values

Photo by Andrea Ferrario on Unsplash
Photo by Andrea Ferrario on Unsplash

I was working on this leetcode question https://leetcode.com/contest/weekly-contest-212/problems/path-with-minimum-effort/ using backtracking and spent some time debugging strange output. This article discusses some pitfalls when using Recursion with global variables, how to handle them, and how to change the code from global to local.

Disclaimer: Backtracking only passing 15/75 test cases and Time Limit Exceeded for the rest, the purpose of this article is to highlight possible issues with global variables rather than give the best solutions. For more beautiful solutions using Binary Search, Dijkstra and Kruskal, watch Alex’s walkthrough (beginning 7:26) at https://www.youtube.com/watch?v=AM__3Zx1XNw&t=2325s&ab_channel=AlexWice

Problem

The problem is to find the path with minimum effort after walking from top left to bottom right with each step allowing 4 directions of up, down, left, right. effort is defined as the maximum absolute difference in values between any 2 consecutive squares.

Notebook containing implementation with global vs no global variable: https://gist.github.com/gitgithan/a818d336c2309852a21d99efd619238d

Backtracking Overview

My backtracking solution was to use a visited 2D array to track visits. Starting from the top-left cell, we try to move in the order of down, right, up, left (this order reaches the destination faster than some other orders, so the global min can be updated earlier, and used to bound/speed up the exploration of future paths) if within rectangle bounds and not visited before. Before moving (recursing), the visit is marked so future attempts to visit will return False for if valid().

Along the way, the effort (intialized to 0) of the path is updated using abs difference between the cell we are going to visit and current cell. If we reach base case (bottom-right cell), return the effort.

Once a single direction of recursion is complete, we update the global minimum min_effort (initialized to math.inf) and unmark the cell in that direction.

Once all 4 directions from the current cell is done, we return math.inf back up the call stack so it does not wrongly influence the min() of the caller.

BUG

This output of five 2, followed by two inf was mindboggling. It looked like the global variable min_effort which was updated from inf to 2 after the first solution (1, down to 3, down to 5, right to 3, right to 5) went back to inf! The final answer(path of 1, 2, 3, 4, 5) was also wrongly inf instead of 1.

Those five 2 correspond to the algorithm backtracking from destination 5 to 4,3,2,8,3,5 because all these have all 4 directions either visited or out of bounds, so the next path to try is to go right from 1,0 to 1,1 (3 to 8).

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

The problem is with the line min_effort = min(min_effort,find_path(...)) Because python evaluates arguments from left to right, the global variable min_effort was already evaluated before entering the recursion, so whatever happens in the recursion (including updates to global variable) has no effect on min_effort.

At the scope of the 3 in bottom middle of the grid, the algorithm has not yet found a successful path (the 1st path being 1,3,5,3,5), so min_effort was still math.inf at that moment, and min(math.inf,math.inf) became inf.

3 Fixes

  1. Swap arguments

A fix is to simply swap the order of arguments to min_effort = min(find_path(...), min_effort). This gives the recursion a chance to update the global variable first before comparison.

  1. Save into variable first

If you still wanted to maintain the old order as a matter of preference, the recursion can be calculated and saved into a variable first.

recursion_res = find_path(...)
min_effort = min(min_effort, recursion_res)
  1. Remove global variables completely

This was prompted by Leetcode giving wrong test results running all test cases, but running the failing case individually as custom input gives the correct result. If you insist on using globals on leetcode, copy the result, clear the global, and return the copied result so the cleared global is ready for the next test case.

Two changes:

  1. Add the previously global variable to recursive function signature find_path(...,min_effort)
  2. Return min_effort rather than math.inf

This will ensure the minimum effort path is always propagated through the recursive calls. If you ask why not return min_effort while using global variable, that is workable too, but unnecessary, since if you avoid the gotcha mentioned above, min_effort would have been updated to a non-inf value before the min(min_effort,find_path(...))comparison, so even if the 2nd argument returns math.inf, the 1st argument will always be updated to the correct value once any path first reaches the destination. Also, math.inf felt more representative of a "no solution/bad value".

However, the argument in support of return min_effort rather than return math.inf is that it more accurately represents the most updated program state. Also, we can totally avoid the gotcha handling (the 1st two fixes described) and use min(min_effort,find_path(...)) directly because with return min_effort the 2nd argument will always be updated, so a "pre-recursion evaluated" min_effort that could contain its initialized math.inf in the 1st argument causes no harm. (exactly opposite situation of the previous paragraph).

Improving the solution

Since we are looking for the global minimum, any path can be influenced by the results of any other path. This offers a chance for the current best result to short-circuit future paths once they are found to have longer effort than the current min_effort . This can be achieved by wrapping the backtracking section (visit,recurse,unvisit) with an extra check if updated_effort < min_effort: to largely reduce exploration steps, using "less than" because there is no point trying something that won’t reduce the current best.

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

Comparing global vs local

Global pros:

  1. Lax return values allowed ( math.inf or min_effort )
  2. Convenient coding (less parameter passing and simpler recursive functions)

Global cons:

  1. Don’t gel with online coding platforms (risky for job interview automated coding assessments)
  2. Constantly have to be aware of side effects and variables not within current stack
  3. Sensitive to function argument ordering (the root of all these troubles)

Local pros:

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

Local cons:

  1. More verbose function signature (more items to track means longer signature)
  2. Lose ability to return math.inf , have to return min_effort to propagate updated results back to rest of program

Doing it wrong more valuable than doing it right

When using globals, if I had returned min_effort or coded properly using fix 2 above initially, I would not have seen this gotcha at all. It’s a blessing in disguise that returning the most intuitively correct value and being lazy with (possibly) extraneous variable assignments allowed me to strengthen my understanding of python evaluation order and debugging skills.


Related Articles