Re:Tree traversal without recursion: the tree as a state mac...
by rrobukef on Tuesday September 03, 2019 @02:34PM
(#20869635)
You could simulate the recursion with an iteration, a depth byte and a stack-array of 32 pointers (64 for overkill). This removes the frame pointer and makes the temporaries clear too.
[ Parent
| on HN ]
Re:Tree traversal without recursion: the tree as a state mac...
by wahern on Tuesday September 03, 2019 @04:45PM
(#20870971)
But that's not recursion, which pretty much by definition implies the use of repeated invocations of the same function(s). Explicitly building a stack is exactly what the article was discussing, though it's far more clever than the obvious approach. I've seen AVL implementations that use an explicit array for maintaining a stack in lieu of recursion or parent pointers.
In any event, you always need a stack of some sort. Recursion is one way to accomplish that, but saying that you're simulating recursion by explicitly building a stack reverses the categories.