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

[Junio C Hamano <gitster@pobox.com>]

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.