Today I want to share a Python trickt hat has been very useful in our UI code for Measure Killer. Credit for this suggestion to Pedro Smiderle, my college at Brunner BI and an absolute python legend.
The problem is simple to describe: when a user checks or unchecks an item in a tree (basically QTreeWidgetItem with checkboxes), all of that items descendants (we also call them child items, or simply children) should have the same state. The simple and “quick” solution is a recursive method that visits each child, then each grandchild, and so on. It does work, until the tree gets deep enough to trigger the feared RecursionError.
Next, I’ll explain why that happens, then show the iterative Depth First Search (DFS) approach we use to fix the problem and how this can be useful in any similar situation where recursion is needed.
The problem: recursion in Python
At first we tried using a “direct” recursive approach, note that the function is called within it self in the last line (that’s why it is recursive):
def update_child_check_state(self, parent_item, state):
for i in range(parent_item.childCount()):
child = parent_item.child(i)
if not child.isHidden():
if (child.flags() & Qt.ItemIsEnabled) and (child.flags() & Qt.ItemIsUserCheckable):
child.setCheckState(0, state)
self.update_child_check_state(child, state)The basic idea behind this method is simple: “for each child, do the same thing to its children”, but Python default recursion limit is around 1000 function calls and large trees (which are not uncommon to see in Measure Killer) can easily past that and raise RecursionError. You can raise the limit using the sys package, but that is not ideal and it’s a terrible practice (Not gonna go into details why, but, dear reader, you can imagine how terrible it can get).
The fix: Iterative DFS with an explicit stack
Instead of using Python’s call stack, we manage our own stack with a list, this completely avoids the recursion limit:
def update_child_check_state_bulk(self, parent_item: CustomTreeWidgetItem, state: Qt.CheckState):
"""
Update the check state of all child items to match the parent's state.
Args:
parent_item (CustomTreeWidgetItem): The upstream tree item widget object
state (Qt.CheckState): The check state to set for all child items
"""
stack = [parent_item]
while stack:
current_item = stack.pop()
for i in range(current_item.childCount()):
child = current_item.child(i)
if not child.isHidden():
if child.flags() & Qt.ItemIsEnabled and child.flags() & Qt.ItemIsUserCheckable:
child.setCheckState(0, state)
stack.append(child)Explaining the code: We start with the parent item (An example of a Qt Tree widget can be seen in Image 1 below). While there are items to process, we pop one (it removes the last item from the list and saves it to a variable), then update its children with the same state as its parent (check or unchecked) , and append those children in the stack (the list) to process later. This is “Depth First Search”, but iteratively. This “trick” can handle any sort of deep tree without reaching the recursion limit.
Conclusion
The iterative DFS is a great substitute for a recursive method, without any recursion limits. I used a Qt UI widget as an example, but any cases where you have to perform a recursive traversal could use this technique to escape from the RecurssionError. You might not see any performance improvements, but at least you will be able to get rid of the recursion limit and avoid changing it using the sys package for example.
