Recursion Tracing (Regex Assignment 2)

Back to the post of recursion, there are two kinds to trace a recursion algorithm. Tracing step by step and tracing by faith. This assignment is about converting a string of regex to regex tree and marching a regex tree to a string of binary. Converting a string of regex to regex tree, we iterate each token of the string and build it into the tree when we counter an end parenthesis. Is not hard to trace, since being just one level. What is challenged is second part of the assignment, marching a regex tree to a string of binary, especially star node.

There is this particular example:
((1.(0|1)*).0) matches any string that starts with '1' and ends with '0'.  Lets say that is marching with '11111' and the bar and dot node work as it should be. The hard part is to implement the starnode to know where to  stop tracing the string of binary. For example if the starnode doesn't know where to stop, it will return True without checking the last dot node. The solution is to check every possible split of the string of binary:
...
        elif isinstance(tree_regex, StarNode):
            if len(partition) is 0:
                return True
            else:
                for i in range(len(partition), 0, -1):
                    if match(tree_regex.children[0], partition[:i]):
                        return match(tree_regex, partition[i:])
                return False
...

For human to trace step by step is really hard, since each split is a level deeper. Human are only good at tracing two levels of details. This case is the perfect example to trace it by faith. First, just try tracing a simple string, like '110' and '111'; if it work, then hope that it will work with complex string of binary.

This assignment helps me to realize why tracing step by step is hard for human.