| ▲ | dinobones 3 days ago | |
I’m surprised this isn’t a more common and well known issue. I stumbled upon this issue when trying to convert a recursive DFS to iterative because my recursive DFS was running out of stack space. The solution produced by this iterative version was wrong, completely different from the recursive implementation. It’s fascinating how many primitive, basic algorithms are probably implemented incorrectly but work just well enough that no one ever cares or notices… reminds me of how so many text books have an incorrect or overflowing version of binary search. | ||
| ▲ | imtringued 3 days ago | parent | next [-] | |
Why would it be a common issue? People usually implement graph traversal first and only after that do they choose a FIFO queue for BFS or a stack for DFS as their data structure. | ||
| ▲ | pss314 3 days ago | parent | prev [-] | |
reminds me of how so many text books have an incorrect or overflowing version of binary search. Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken https://research.google/blog/extra-extra-read-all-about-it-n... | ||