On 22/05/09 02:16PM, Junio C Hamano wrote: > Plato Kiorpelidis <kioplato@xxxxxxxxx> writes: > > > Simplify dir_iterator_advance() by converting from iterative to > > recursive implementation. This conversion makes dir-iterator more > > maintainable for the following reasons: > > * dir-iterator iterates the file-system, which is a tree structure. > > Traditionally, tree traversals, in textbooks, lectures and online > > sources are implemented recursively and not iteratively. Therefore > > it helps reduce mental load for readers, since it's easier to follow > > as it reminds of the same tree traversals we use on tree structures. > > Careful. > > Many algorithms that are taught in the recursive form in textbooks > are turned into iterative in production systems for a reason. To > avoid too deep a recursion wasting too much stack space. A loop > with management of work items using in-program data structures like > stack or queue often makes a large traversal bearable. > > The most obvious example is our history traversal code. History > stored in Git is a tree structure, but no sane reimplementation of > Git (well, at least those that want to be able to deal with a > history larger than a toy project) would implement "git log" using a > recursive algorithm. That's a good point, I didn't think about that. It's also something that's objective, so it's easier to reach a conclusion. This whole refactoring of dir_iterator_advance() is a matter of opinion on what's more readable or not. In this case, however, the dir_iterator_advance() is performing tail recursion which doesn't require stack space. It reuses the stack frame from the current call for the next call. Does this still pose a problem and why? If it does, I've got no problem to work with the existing iterative implementation. Thanks, Plato
