Почему ls-R назван “рекурсивным” списком?

Когда Вы думаете об этом, "рекурсивный" имеет смысл для команд, которые действуют на каталоги и их файлы и каталоги и их файлы и каталоги и их файлы и каталоги и их файлы.........

...., пока на всем дереве от указанной точки вниз не управляла команда в этом случае, перечисляющем содержание никаких подкаталогов никаких подкаталогов никаких подкаталогов.........., которые существуют под аргументом (аргументами) команды

-R для рекурсии, которую можно было свободно называть "неоднократно".

Берут этот код, например:

───────────────────────────────────────────────────────────────────────────────
$ mkdir -p temp/a
───────────────────────────────────────────────────────────────────────────────
$ mkdir -p temp/b/1
───────────────────────────────────────────────────────────────────────────────
$ mkdir -p temp/c/1/2
───────────────────────────────────────────────────────────────────────────────
$ ls -R temp
temp:
a  b  c

temp/a:

temp/b:
1

temp/b/1:

temp/c:
1

temp/c/1:
2

temp/c/1/2:

-p в создании каталогов позволяет, Вы к массе создаете каталоги с единственной командой. Если один или несколько главных средних каталогов уже существует, это не ошибка, и средние более низкие каталоги создаются.

Затем ls -R рекурсивно списки каждый каталог, запускающийся с временного файла и работающий, это - путь вниз дерево ко всем ответвлениям.

Теперь позволяют нам посмотреть на дополнение к эти ls -R команда, т.е. эти tree команда:

$ tree temp
temp
├── a
├── b
│   └── 1
└── c
    └── 1
        └── 2

6 directories, 0 files

, Как Вы видите tree, выполняет то же, поскольку ls -R кроме более кратко, и смейте, я говорю "более симпатичный".

Теперь позволяют нам посмотреть на то, как рекурсивно удалить каталоги, которые мы просто создали в одной простой команде:

$ rm -r temp

Это рекурсивно удаляет temp и все подкаталоги под ним. т.е. temp/a, temp/b/1 и temp/c/1/2 плюс средние промежуточные каталоги.

Вот простое объяснение, оно имеет смысл, потому что когда дело доходит до отображения содержания подкаталогов, та же функция уже знает, что сделать с каталогом. Поэтому это просто должно назвать себя на каждом подкаталоге для получения того результата!

В псевдокоде это выглядит примерно так:

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

Существуют, в действительности, два тесно двойных вопроса, которые можно задавать.

• Почему процесс обхода является к каждой записи в иерархии файловой системы по сути рекурсивным процессом? Это обращено другими ответами, такими как Zanna и Kaz Wolfe.
• Как метод рекурсии используется в реализации ls? От Вашей формулировки ("Как рекурсия используется в процессе?"), я думаю, что это - часть того, что Вы хотите знать. Этот ответ рассматривает тот вопрос.

Почему это имеет смысл для ls быть реализованным с рекурсивной техникой:

FOLDOC определяет рекурсию как:

Когда функция (или процедура) называет себя. Такая функция вызвана "рекурсивная". Если вызов через одну или несколько других функций затем, эта группа функций вызвана "взаимно рекурсивная".

Естественный способ реализовать ls должен записать функцию, которая создает список из записей файловой системы, которые будут отображены, и другой код, чтобы обработать путь и аргументы опции и отобразить записи, как желаемый. Та функция, очень вероятно, будет реализована рекурсивно.

Во время обработки опции, ls определит, попросили ли работать рекурсивно (будучи вызванным с -R флаг). Если так, функция, которая создает список из записей, которые будут отображены, назовет себя однажды для каждого каталога, кроме которого она перечисляет, . и ... Могут быть отдельные рекурсивные и нерекурсивные версии этой функции, или функция может проверить каждый раз, если она, как предполагается, работает рекурсивно.

Ubuntu /bin/ls, исполняемый файл, который работает, когда Вы работаете ls, обеспечивается GNU Coreutils, и он имеет много функций. В результате его код несколько длиннее и более сложен, чем Вы могли бы ожидать. Но Ubuntu также содержит более простую версию ls, если BusyBox. Можно выполнить это путем ввода busybox ls.

Как busybox ls рекурсия использования:

ls в BusyBox реализован в coreutils/ls.c. Это содержит a 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.

Теперь скажите GDB работать busybox с 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);
                }

Иначе функция просто работает однажды (на каталог, указанный на командной строке).