Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The thing that has the shape of a quadtree is the callgraph. That means there is one call for every instance of the data class, which makes it easy to reason about the code.

See also my answer to the parent: https://news.ycombinator.com/item?id=13306762.



Reading through some ancient conversations...

OK so the callgraph is isomorphic in some sense when using recursion. If this was the intent of the author, it was not clear.

I would still argue that call-graph isomorphism to the data structures they work is of little relevance to software practitioners.

1. Multithreaded algorithms acting on trees do not necessarily have callgraphs that are isomorphic to the trees.

2. As I mentioned elsewhere, arbitrary graph data structures, or even the more constrained subset of DAGS, are not isomorphic to call graphs of the algorithms that work on them. Recursive algorithms have the same exact applicability to these structures as they do quadtrees.

3. Also as I mentioned elsewhere, recursive algorithms can be implemented with loops and an explicit stack without any function calls at all. This is at times the best way to implement algorithms on trees (particularly where trees are deep and the platform has a small stack - yes I've had to do rewrite recursive code because it overflowed a small, non-configurable stack).


> The thing that has the shape of a quadtree is the callgraph

Thanks, I have borrowed your succinct explanation and added it to the essay. MuchIappreciate the insight.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: