As my original introduction to data structures was in the context of C/C++, it’s been interesting recently to see how these translate into a more concise, magical language such as Python. DFS path finding provides a classic example of it making life easier.
A recursive algorithm to find a path between two vertices, as in almost any other language, is trivial.
But trying to generalise this algorithm to find all paths requires the addition of a ‘paths’ variable outside the scope of our beautiful recursive function. Instead of returning the path, we’d do something like paths.append( path ).
A neat way to circumvent this problem would be to turn the function into a generator and yield valid paths to the caller. However recursion throws a spanner in the works as a generator expression only yields to its immediate caller. So we’d have to loop over the recursive call and yield the yields.
Thankfully PEP 380 – Syntax for Delegating to a Subgenerator comes to the rescue, allowing us to treat all yields as originating in the callee.