Re: [PATCH v2 10/15] dir-iterator: refactor dir_iterator_advance()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- May 9, 2022, 21:16 UTC
- Message-ID
- <xmqqr152be4n.fsf@gitster.g>
- In-Reply-To
- <20220509175159.2948802-11-kioplato@gmail.com>
Plato Kiorpelidis <kioplato@gmail.com> writes:
Show 8 quoted lines
> 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.