Pertanyaan Mengapa ls -R disebut daftar "rekursif"?


aku mengerti itu ls -R menampilkan daftar direktori. Tapi mengapa itu rekursif? Bagaimana rekursi digunakan dalam proses?


35
2018-01-23 18:50


asal


Intuisi adalah bahwa direktori dan subdirektori mereka dapat dengan mudah dimodelkan menggunakan pohon. Algoritma untuk berjalan di pohon biasanya bersifat rekursif. - Kevin
@Kevin Saya pikir tidak perlu menggunakan konsep pohon untuk menjawab setiap pertanyaan - jawabannya adalah sesederhana itu ls menemukan direktori yang secara rekursif mencantumkan direktori itu. - immibis


Jawaban:


Pertama, mari kita mendefinisikan struktur folder yang sewenang-wenang:

.
├── 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]

Ketika kita melakukannya ls, kita mendapatkan output dari folder dasar saja:

a1 a2 a3 a4

Namun, saat kami menelepon ls -R, kita mendapatkan sesuatu yang berbeda:

.:
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:

Seperti yang Anda lihat, itu berjalan ls pada folder dasar, dan kemudian semua folder anak. Dan semua folder cucu, ad infinitum. Secara efektif, perintah akan melalui setiap folder secara rekursif sampai menyentuh ujung pohon direktori. Pada titik itu, ia kembali ke cabang pohon dan melakukan hal yang sama untuk setiap sub-folder, jika ada.

Atau, dalam pseudo-code:

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
        }
    }
}

Dan karena saya bisa, a implementasi referensi Java yang sama.


66
2018-01-23 18:59





Ada, pada dasarnya, dua pertanyaan yang terkait erat yang mungkin Anda tanyakan.

  • Mengapa proses berjalan ke setiap entri dalam hierarki sistem file merupakan proses rekursif yang inheren? Ini diatasi dengan jawaban lain, seperti Zanna dan Kaz Wolfe.
  • Bagaimana caranya teknik rekursi yang digunakan dalam implementasi ls? Dari ungkapan Anda ("Bagaimana rekursi yang digunakan dalam proses?"), Saya pikir ini adalah bagian dari apa yang ingin Anda ketahui. Jawaban ini menjawab pertanyaan itu.

Mengapa itu masuk akal untuk ls untuk diimplementasikan dengan teknik rekursif:

FOLDOC mendefinisikan rekursi sebagai:

Ketika sebuah fungsi (atau prosedur) memanggil dirinya sendiri. Fungsi seperti itu   disebut "rekursif". Jika panggilan dilakukan melalui satu atau beberapa fungsi lain   maka kelompok fungsi ini disebut "saling rekursif".

Cara alami untuk menerapkan ls adalah menulis fungsi yang membangun daftar entri filesystem yang akan ditampilkan, dan kode lain untuk memproses jalur dan argumen opsi dan untuk menampilkan entri seperti yang diinginkan. Fungsi itu sangat mungkin diterapkan secara rekursif.

Selama pemrosesan opsi, ls akan menentukan apakah telah diminta untuk beroperasi secara rekursif (dengan dipanggil dengan -R bendera). Jika demikian, fungsi yang membangun daftar entri yang akan ditampilkan akan memanggil dirinya sendiri sekali untuk setiap direktori yang terdaftar, kecuali . dan ... Mungkin ada versi rekursif dan non-rekursif terpisah dari fungsi ini, atau fungsi dapat memeriksa setiap kali jika seharusnya beroperasi secara rekursif.

Ubuntu /bin/ls, eksekusi yang berjalan saat Anda menjalankan ls, disediakan oleh GNU Coreutils, dan itu banyak fitur. Hasil dari, kodenya agak lebih panjang dan lebih rumit dari yang Anda duga. Tetapi Ubuntu juga berisi versi yang lebih sederhana ls, disediakan oleh BusyBox. Anda dapat menjalankan ini dengan mengetik busybox ls.

Bagaimana busybox ls menggunakan rekursi:

ls di BusyBox diimplementasikan di coreutils/ls.c. Ini berisi scan_and_display_dirs_recur() fungsi yang diminta untuk mencetak pohon direktori secara rekursif:

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);
        }
    }
}

Garis tempat pemanggilan fungsi rekursif terjadi adalah:

                    scan_and_display_dirs_recur(dnd, 0);

Melihat panggilan fungsi rekursif saat terjadi:

Anda dapat melihat ini dalam operasi jika Anda menjalankan busybox ls di debugger. Pertama instal simbol debug oleh memungkinkan paket -dbgsym.ddeb lalu menginstal busybox-static-dbgsym paket. Memasang gdb juga (itulah debugger).

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

Saya menyarankan untuk melakukan debug coreutils ls pada pohon direktori sederhana.

Jika Anda tidak memiliki satu berguna, buat satu (ini bekerja dengan cara yang sama seperti mkdir -p perintah masuk Jawaban WinEunuuchs2Unix):

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

Dan mengisinya dengan beberapa file:

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

Anda dapat memverifikasi busybox ls -R foo bekerja seperti yang diharapkan, menghasilkan output ini:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

Buka busybox di debugger:

gdb busybox

GDB akan mencetak beberapa informasi tentang dirinya sendiri. Maka seharusnya mengatakan sesuatu seperti:

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

(gdb) adalah prompt Anda di debugger. Hal pertama yang Anda katakan GDB lakukan pada prompt ini adalah mengatur breakpoint di awal scan_and_display_dirs_recur() fungsi:

b scan_and_display_dirs_recur

Saat Anda menjalankannya, GDB seharusnya memberi tahu Anda sesuatu seperti:

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

Sekarang beri tahu GDB untuk dijalankan busybox dengan ls -R foo (atau nama direktori apa pun yang Anda inginkan) sebagai argumennya:

run ls -R foo

Anda mungkin melihat sesuatu seperti ini:

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.

Jika Anda melihatnya No such file or directory, seperti di atas, tidak apa-apa. Tujuan demonstrasi ini hanya untuk melihat kapan scan_and_display_dirs_recur() fungsi telah dipanggil, sehingga GDB tidak perlu memeriksa kode sumber yang sebenarnya.

Perhatikan bahwa debugger mengenai breakpoint bahkan sebelum entri direktori dicetak. Itu rusak pada entrace untuk fungsi itu, tetapi kode dalam fungsi itu harus dijalankan untuk direktori apa saja yang akan dicacah untuk dicetak.

Untuk memberi tahu GDB untuk melanjutkan, jalankan:

c

Setiap kali scan_and_display_dirs_recur() disebut, breakpoint akan dipukul lagi, sehingga Anda akan bisa melihat rekursi dalam tindakan. Sepertinya ini (termasuk (gdb) prompt dan perintah Anda):

(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]

Fungsi ini recur dalam namanya ... apakah BusyBox hanya menggunakannya ketika -R bendera diberikan? Di debugger, ini mudah ditemukan:

(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]

Bahkan tanpa -R, implementasi khusus ini ls menggunakan fungsi yang sama untuk mencari tahu entri filesystem apa yang ada dan menunjukkannya.

Ketika Anda ingin keluar dari debugger, katakan saja:

q

Bagaimana scan_and_display_dirs_recur() tahu apakah itu harus memanggil dirinya sendiri:

Khususnya bagaimana cara kerjanya berbeda ketika -R bendera dilewatkan? Meneliti Kode sumber (yang mungkin bukan versi yang tepat pada sistem Ubuntu Anda) mengungkapkan bahwa ia memeriksa struktur data internal G.all_fmt, di mana ia menyimpan opsi apa yang telah dimohon dengan:

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

(Jika BusyBox dikompilasi tanpa dukungan untuk -R, maka itu juga tidak akan mencoba untuk menampilkan entri filesystem secara rekursif; itulah yang ENABLE_FEATURE_LS_RECURSIVE bagian tentang.)

Hanya bila G.all_fmt & DISP_RECURSIVE adalah benar apakah kode yang berisi panggilan fungsi rekursif dijalankan.

                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);
                }

Jika tidak, fungsi hanya berjalan sekali (per direktori yang ditentukan pada baris perintah).


22
2018-01-24 07:48



Sekali lagi, Eliah datang dengan jawaban yang sangat komprehensif. +1 yang layak. - Kaz Wolfe
Oh, jadi itu bahkan bukan rekursi ekor. Ini berarti ada beberapa isi direktori, daftar yang akan merusak busybox karena tumpukan overflow (meskipun itu akan menjadi sarang yang sangat dalam). - Ruslan
Ini luar biasa. Pada dasarnya Anda menyediakan OP dengan pelajaran cepat dalam debugging sehingga mereka dapat memahami dengan tepat bagaimana cara kerjanya. Hebat. - Andrea Lazzarotto


Ketika Anda berpikir tentang hal itu, "rekursif" masuk akal untuk perintah yang bertindak pada direktori dan file dan direktori mereka dan file dan direktori mereka dan file dan direktori dan file mereka .........

.... sampai seluruh pohon dari titik yang ditentukan ke bawah telah dioperasikan oleh perintah, dalam hal ini daftar isi dari setiap subdirektori dari setiap subdirektori dari setiap subdirektori .......... yang ada di bawah argumen (s) dari perintah


16
2018-01-23 18:58





-R adalah untuk rekursi, yang bisa disebut "berulang kali".

Ambil kode ini misalnya:

───────────────────────────────────────────────────────────────────────────────
$ 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:

Itu -p dalam membuat direktori memungkinkan Anda membuat direktori secara massal dengan satu perintah. Jika satu atau lebih dari direktori top-middle sudah ada, itu bukan kesalahan dan direktori menengah ke bawah dibuat.

Maka itu ls -R secara rekursif mendaftar setiap direktori yang dimulai dengan temp dan bekerja dengan cara menuruni pohon ke semua cabang.

Sekarang mari kita lihat pelengkap ls -R perintah, yaitu tree perintah:

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

6 directories, 0 files

Seperti yang Anda lihat tree menyelesaikan sama dengan ls -R kecuali lebih ringkas dan berani saya katakan "lebih cantik".

Sekarang mari kita lihat cara menghapus secara rekursif direktori yang baru kita buat dalam satu perintah sederhana:

$ rm -r temp

Ini menghapus secara rekursif temp dan semua sub-direktori di bawahnya. yaitu temp/a, temp/b/1 dan temp/c/1/2 plus direktori tengah di antaranya.


7
2018-01-24 01:07



Jika "ls -R" harus melakukan sesuatu berkali-kali maka Anda akan mendapatkan hasil yang sama beberapa kali;) +1 untuk tree meskipun. Ini alat yang hebat. - Pod
Ya suara miskin kata orang awam. Saya mencoba mencari kata di mainstream sehingga memudahkan tipe non programmer untuk memahami. Saya akan mencoba memikirkan kata yang lebih baik atau menghapusnya nanti. - WinEunuuchs2Unix


Berikut penjelasan sederhana, masuk akal karena ketika datang untuk menampilkan isi subdirektori, fungsi yang sama sudah tahu apa yang harus dilakukan dengan direktori. Oleh karena itu hanya perlu memanggil dirinya sendiri di setiap subdirektori untuk mendapatkan hasil itu!

Dalam pseudocode terlihat seperti ini:

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

5
2018-01-24 20:55