☰

为什么 ls -R 被称为“递归”列表？

tag-icon • tag-icon command-line ls
为什么 ls -R 被称为“递归”列表？

我知道这ls -R会显示目录列表。但为什么是递归的？在此过程中如何使用递归？

答案1

首先，让我们定义一个任意文件夹结构：

.
├── a1 [D]
│   ├── b1 [D]
│   │   ├── c1
│   │   ├── c2 [D]
│   │   │   ├── d1
│   │   │   ├── d2
│   │   │   └── d3
│   │   ├── c3
│   │   ├── c4
│   │   └── c5
│   └── b2 [D]
│       ├── c6
│       └── c7
├── a2 [D]
│   ├── b3 [D]
│   │   ├── c8
│   │   └── c9
│   └── b4 [D]
│       ├── c10 
│       └── c11
├── a3 [D]
│   ├── b5
│   ├── b6
│   └── b7
└── a4 [D]

当我们这样做时ls，我们只会获得基本文件夹的输出：

a1 a2 a3 a4

然而，当我们调用时ls -R，我们得到了一些不同的东西：

.:
a1  a2  a3  a4

./a1:
b1  b2

./a1/b1:
c1  c2  c3  c4  c5

./a1/b1/c2:
d1  d2  d3

./a1/b2:
c6  c7

./a2:
b3  b4

./a2/b3:
c8  c9

./a2/b4:
c10  c11

./a3:
b5  b6  b7

./a4:

如您所见，它ls在基础文件夹上运行，然后在所有子文件夹上运行。然后是所有孙文件夹，以此类推。实际上，该命令正在遍历每个文件夹递归地直到到达目录树的末尾。此时，它会返回树中的一个分支，并对任何子文件夹（如果有）执行相同的操作。

或者，用伪代码来表示：

recursivelyList(directory) {
    files[] = listDirectory(directory)              // Get all files in the directory
    print(directory.name + ":\n" + files.join(" ")) // Print the "ls" output
    for (file : files) {                            // Go through all the files in the directory
        if (file.isDirectory()) {                   // Check if the current file being looked at is a directory
            recursivelyList(directory)              // If so, recursively list that directory
        }
    }
}

因为我可以，参考Java实现一样的。

答案2

实际上，您可能会问两个紧密相关的问题。

  • 为什么遍历文件系统层次结构中的每个条目的过程本质上是一个递归过程？其他答案已经解决了这个问题，例如扎娜的和卡兹·沃尔夫的。
  • 如何技术递归在实现中使用了什么ls？从您的措辞（“递归在过程中是如何使用的？”）来看，我认为这是您想知道的一部分。这个答案解决了这个问题。

ls为什么使用递归技术实现是有意义的：

福多克定义递归作为：

当一个功能（或者程序) 调用自身。这样的函数称为“递归”。如果调用是通过一个或多个其他函数进行的，则这组函数称为“相互递归”。

自然的实现方式ls是编写一个函数来构造要显示的文件系统条目列表，以及处理路径和选项参数并根据需要显示条目的其他代码。该函数很可能以递归方式实现。

在选项处理期间，ls将确定是否已要求其进行递归操作（通过使用标志进行调用-R）。如果是这样，则构建要显示的条目列表的函数将为其列出的每个目录调用一次自身，但.和除外..。此函数可能有单独的递归和非递归版本，或者函数每次都可能检查它是否应该进行递归操作。

Ubuntu 的/bin/ls，即运行 时运行的可执行文件ls，由以下程序提供：GNU 核心实用程序，并且它许多功能。因此，它的代码比您预期的要长一些，也复杂一些。但 Ubuntu 还包含一个更简单的版本ls，由忙碌盒子。您可以通过输入 来运行它busybox ls。

如何busybox ls使用递归：

lsBusyBox 的实现coreutils/ls.c。它包含一个scan_and_display_dirs_recur()函数，可以调用该函数来递归打印目录树：

static void scan_and_display_dirs_recur(struct dnode **dn, int first)
{
    unsigned nfiles;
    struct dnode **subdnp;

    for (; *dn; dn++) {
        if (G.all_fmt & (DISP_DIRNAME | DISP_RECURSIVE)) {
            if (!first)
                bb_putchar('\n');
            first = 0;
            printf("%s:\n", (*dn)->fullname);
        }
        subdnp = scan_one_dir((*dn)->fullname, &nfiles);
#if ENABLE_DESKTOP
        if ((G.all_fmt & STYLE_MASK) == STYLE_LONG || (G.all_fmt & LIST_BLOCKS))
            printf("total %"OFF_FMT"u\n", calculate_blocks(subdnp));
#endif
        if (nfiles > 0) {
            /* list all files at this level */
            sort_and_display_files(subdnp, nfiles);

            if (ENABLE_FEATURE_LS_RECURSIVE
             && (G.all_fmt & DISP_RECURSIVE)
            ) {
                struct dnode **dnd;
                unsigned dndirs;
                /* recursive - list the sub-dirs */
                dnd = splitdnarray(subdnp, SPLIT_SUBDIR);
                dndirs = count_dirs(subdnp, SPLIT_SUBDIR);
                if (dndirs > 0) {
                    dnsort(dnd, dndirs);
                    scan_and_display_dirs_recur(dnd, 0);
                    /* free the array of dnode pointers to the dirs */
                    free(dnd);
                }
            }
            /* free the dnodes and the fullname mem */
            dfree(subdnp);
        }
    }
}

发生递归函数调用的行是：

                    scan_and_display_dirs_recur(dnd, 0);

观察递归函数调用的发生过程：

busybox ls如果你在调试器中运行，你可以看到它正在运行。首先安装调试符号经过启用 -dbgsym.ddeb 包然后安装busybox-static-dbgsym软件包。gdb也安装（这是调试器）。

sudo apt-get update
sudo apt-get install gdb busybox-static-dbgsym

我建议coreutils ls在简单的目录树上进行调试。

如果你手边没有，可以创建一个（其工作方式mkdir -p与WinEunuuchs2Unix 的答案)：

mkdir -pv foo/{bar/foobar,baz/quux}

并用一些文件填充它：

(shopt -s globstar; for d in foo/**; do touch "$d/file$((i++))"; done)

您可以验证busybox ls -R foo工作是否按预期进行，并产生以下输出：

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

busybox在调试器中打开：

gdb busybox

GDB 将打印一些有关其自身的信息。然后它应该会显示类似以下内容的内容：

Reading symbols from busybox...Reading symbols from /usr/lib/debug/.build-id/5c/e436575b628a8f54c2a346cc6e758d494c33fe.debug...done.
done.
(gdb)

(gdb)是调试器中的提示符。在此提示符下，您要告诉 GDB 做的第一件事是在函数开头设置断点scan_and_display_dirs_recur()：

b scan_and_display_dirs_recur

当你运行该程序时，GDB 应该会告诉你类似的信息：

Breakpoint 1 at 0x5545b4: file coreutils/ls.c, line 1026.

现在告诉 GDBbusybox使用（或任何你想要的目录名）作为其参数来运行：ls -R foo

run ls -R foo

你可能会看到类似这样的内容：

Starting program: /bin/busybox ls -R foo

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6c60, first=1) at coreutils/ls.c:1026
1026    coreutils/ls.c: No such file or directory.

如果您确实看到了No such file or directory，如上所示，那没关系。此演示的目的只是查看函数何时scan_and_display_dirs_recur()被调用，因此 GDB 不需要检查实际源代码。

请注意，调试器在打印任何目录条目之前就已命中断点。它在入口到该函数，但该函数中的代码必须运行才能枚举要打印的任何目录。

要告诉 GDB 继续，请运行：

c

每次scan_and_display_dirs_recur()调用时，断点都会再次被触发，因此您将看到递归的实际操作。它看起来像这样（包括提示符(gdb)和您的命令）：

(gdb) c
Continuing.
foo:
bar    baz    file0

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cb0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/bar:
file1   foobar

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cf0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/bar/foobar:
file2

foo/baz:
file3  quux

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cf0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/baz/quux:
file4
[Inferior 1 (process 2321) exited normally]

该函数的recur名称中包含... BusyBox 是否仅在-R指定标志时才使用它？在调试器中，很容易发现这一点：

(gdb) run ls foo
Starting program: /bin/busybox ls foo

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6c60, first=1) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.
bar    baz    file0
[Inferior 1 (process 2327) exited normally]

即使没有-R，这个特定的实现也ls使用相同的函数来找出存在的文件系统条目并显示它们。

当你想退出调试器时，只需告诉它：

q

如何scan_and_display_dirs_recur()知道是否应该调用自己：

具体来说，当-R？检查源代码（可能不是您的 Ubuntu 系统上的确切版本）显示它会检查其内部数据结构G.all_fmt，其中存储了调用它的选项：

            if (ENABLE_FEATURE_LS_RECURSIVE
             && (G.all_fmt & DISP_RECURSIVE)

（如果 BusyBox 编译时不支持-R，那么它也不会尝试递归地显示文件系统条目；这就是本ENABLE_FEATURE_LS_RECURSIVE部分的内容。）

仅当G.all_fmt & DISP_RECURSIVE为真时，包含递归函数调用的代码才会运行。

                struct dnode **dnd;
                unsigned dndirs;
                /* recursive - list the sub-dirs */
                dnd = splitdnarray(subdnp, SPLIT_SUBDIR);
                dndirs = count_dirs(subdnp, SPLIT_SUBDIR);
                if (dndirs > 0) {
                    dnsort(dnd, dndirs);
                    scan_and_display_dirs_recur(dnd, 0);
                    /* free the array of dnode pointers to the dirs */
                    free(dnd);
                }

否则，该函数只运行一次（根据命令行上指定的目录）。

答案3

当您考虑它时，“递归”对于作用于目录及其文件以及目录及其文件以及目录及其文件以及目录及其文件的命令是有意义的.........

....直到从指定点向下的整个树都被命令操作，在这种情况下列出命令参数下存在的任何子目录的任何子目录的任何子目录的内容..........

答案4

这是一个简单的解释，这是有道理的，因为当显示子目录的内容时，相同的函数已经知道如何处理目录。因此它只需要在每个子目录上调用自身即可获得该结果！

在伪代码中它看起来像这样：

recursive_ls(dir)
    print(files and directories)
    foreach (directoriy in dir)
        recursive_ls(directory)
    end foreach
end recursive_ls

相关内容