Re: [PATCH v2 10/15] dir-iterator: refactor dir_iterator_advance()

[Plato Kiorpelidis <kioplato@gmail.com>]

On 22/05/09 02:16PM, Junio C Hamano wrote:
> Plato Kiorpelidis <kioplato@gmail.com> 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