我正在开发一个存储类似于文件系统inode树的内容的系统。它已经有了一个与ls命令等价的命令，但是它还不支持递归选项。我正在研究添加递归选项的实现选项我希望最大程度地熟悉那些知道POSIX的用户，并最大限度地提高对编写消费输出的脚本的可移植性。
似乎ls可以通过深度优先遍历或宽度优先遍历来实现。然而，对于某个特定的遍历顺序是由规范决定的，还是作为实现选项留下来的，我还没有找到一个明确的答案。
在POSIX documentation for ls -R中，我找不到任何具体的答案。这是我唯一能找到的与递归实现相关的语句：
在处理-r选项时，实现需要遍历任意深度。对深度的唯一限制应该基于物理存储的耗尽，以跟踪未经更改的目录。
我还尝试查看ls -R的文档。同样，我在那里没有找到遍历顺序的具体语句。
对于一些经验测量，我在centos盒上进行了一个测试，其行为显然是深度优先遍历。
> uname -a
Linux centos 3.10.0-229.el7.x86_64 #1 SMP Fri Mar 6 11:36:42 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux
> yum info coreutils
Loaded plugins: fastestmirror
Repodata is over 2 weeks old. Install yum-cron? Or run: yum makecache fast
Loading mirror speeds from cached hostfile
* base: mirror.pac-12.org
* elrepo: ftp.osuosl.org
* epel: linux.mirrors.es.net
* extras: repos.lax.quadranet.com
* updates: ftp.osuosl.org
Installed Packages
Name : coreutils
Arch : x86_64
Version : 8.22
Release : 11.el7
Size : 14 M
Repo : installed
From repo : anaconda
Summary : A set of basic GNU tools commonly used in shell scripts
URL : http://www.gnu.org/software/coreutils/
License : GPLv3+
Description : These are the GNU core utilities. This package is the combination of
: the old GNU fileutils, sh-utils, and textutils packages.
> tree testTraversal/
testTraversal/
├── dir1
│ └── dir8
│ └── dir9
│ └── dir10
├── dir2
│ ├── dir4
│ │ └── dir5
│ ├── dir6
│ ├── file1
│ └── file2
├── dir3
└── dir4
└── dir5
└── dir6
└── dir7
├── file3
├── file4
└── file5
> ls -R testTraversal/
testTraversal/:
dir1/ dir2/ dir3/ dir4/
testTraversal/dir1:
dir8/
testTraversal/dir1/dir8:
dir9/
testTraversal/dir1/dir8/dir9:
dir10/
testTraversal/dir1/dir8/dir9/dir10:
testTraversal/dir2:
dir4/ dir6/ file1 file2
testTraversal/dir2/dir4:
dir5/
testTraversal/dir2/dir4/dir5:
testTraversal/dir2/dir6:
testTraversal/dir3:
testTraversal/dir4:
dir5/
testTraversal/dir4/dir5:
dir6/
testTraversal/dir4/dir5/dir6:
dir7/
testTraversal/dir4/dir5/dir6/dir7:
file3 file4 file5
我不知道这是规范规定的行为，还是GNU核心实用程序的实现细节。
我自己的观察是，文件系统中的目录结构往往比深度更宽这将表明，深度优先通常是更节省内存的实现选择，尽管可以提出反例，其中宽度优先将更节省内存。
规范中是否规定了遍历顺序？如果不是，那么深度优先遍历在实现中是否被广泛使用，因此它是一个比宽度优先更安全的假设？
最佳答案
coreutils的确是深度优先。busybox是深度优先bsd/os x是深度优先的（实验性的；源是不可读的）。我希望大多数实现都是深度优先的，因为递归很容易实现，而且posix对路径长度的限制非常严格地限制了深度优先遍历的内存/堆栈使用。