Every path the recursion takes: 481 calls over 25 subproblems

Every path the recursion takes: 481 calls over 25 subproblems

The subproblems of edit distance between abca and bcab, with three arrows out of each one — substitute, delete, insert. The number in a cell is how many distinct routes from the corner arrive at it, and their sum, 481, is the number of calls the plain recursion makes. The graph has 25 nodes and the recursion walks it 19.2 times over on average.

Drawn at 700 × 514, wide on the page. Everything above is what recursion-dag returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

3 essays call recursion-dag. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.