Dapatkah dan apakah kompiler mengubah logika rekursif ke logika non-rekursif yang setara?

15

Saya sudah belajar F # dan itu mulai mempengaruhi bagaimana saya berpikir ketika saya pemrograman C #. Untuk itu, saya telah menggunakan rekursi ketika saya merasa hasilnya meningkatkan keterbacaan dan saya tidak bisa membayangkan itu berakhir pada stack overflow.

Hal ini membuat saya bertanya apakah kompiler dapat secara otomatis mengonversi fungsi rekursif ke bentuk non-rekursif yang setara?

programming-languages compiler recursion Aaron Anodide
sumber
optimisasi panggilan ekor adalah contoh dasar yang bagus tetapi hanya berfungsi jika Anda memiliki return recursecall(args);rekursi, hal-hal yang lebih kompleks dimungkinkan dengan membuat tumpukan eksplisit dan memutarnya, tetapi saya ragu mereka akan
ratchet freak
@ scratchet freak: Rekursi tidak berarti "perhitungan yang menggunakan tumpukan".
Giorgio
1
@ Giorgio Saya tahu tetapi tumpukan adalah cara termudah untuk mengubah rekursi menjadi satu loop
ratchet freak

Jawaban:

21

Ya, beberapa bahasa dan pelengkap akan mengubah logika rekursif ke logika non-rekursif. Ini dikenal sebagai pengoptimalan panggilan ekor - perhatikan bahwa tidak semua panggilan rekursif dapat dioptimalkan panggilan ekor. Dalam situasi ini, kompiler mengenali fungsi dari form:

int foo(n) {
  ...
  return bar(n);
}

Di sini, bahasa dapat mengenali bahwa hasil yang dikembalikan adalah hasil dari fungsi lain dan mengubah panggilan fungsi dengan bingkai tumpukan baru menjadi lompatan.

Sadarilah bahwa metode faktorial klasik:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

adalah tidak ekor panggilan optimizatable karena pemeriksaan yang diperlukan pada kembali.

Untuk membuat panggilan ekor ini dapat dioptimalkan,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Kompilasi kode ini dengan gcc -O2 -S fact.c (-O2 diperlukan untuk mengaktifkan optimisasi dalam kompiler, tetapi dengan lebih banyak optimasi dari -O3 semakin sulit bagi manusia untuk membaca ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

Satu dapat melihat di segmen .L4 , jnedaripada call(yang melakukan panggilan subrutin dengan bingkai tumpukan baru).

Harap perhatikan bahwa ini dilakukan dengan C. Optimasi panggilan ekor di java sulit dan tergantung pada implementasi JVM - pengulangan ekor + java dan pengoptimalan pengulangan ekor + pengoptimalan adalah set tag yang baik untuk dijelajahi. Anda mungkin menemukan bahasa JVM lainnya dapat mengoptimalkan rekursi ekor lebih baik (coba clojure (yang membutuhkan pengulangan untuk mengoptimalkan panggilan bolak-balik ), atau scala).

Komunitas
sumber
1
Saya tidak yakin inilah yang diminta OP. Hanya karena runtime menghabiskan atau tidak menggunakan ruang stack dengan cara tertentu, tidak berarti fungsi tersebut tidak rekursif.
1
@MattFenwick Bagaimana maksudmu? "Ini membuat saya bertanya apakah kompiler dapat secara otomatis mengonversi fungsi rekursif ke bentuk non-rekursif yang setara" - jawabannya adalah "ya dalam kondisi tertentu". Syaratnya diperlihatkan, dan ada beberapa gotcha di beberapa bahasa populer lainnya dengan optimasi panggilan ekor yang saya sebutkan.
9

Tapak dengan hati-hati.

Jawabannya adalah ya, tetapi tidak selalu, dan tidak semuanya. Ini adalah teknik yang menggunakan beberapa nama berbeda, tetapi Anda dapat menemukan beberapa informasi yang cukup definitif di sini dan di wikipedia .

Saya lebih suka nama "Tail Call Optimization" tetapi ada orang lain dan beberapa orang akan membingungkan istilah itu.

Yang mengatakan ada beberapa hal penting untuk disadari:

  • Untuk mengoptimalkan panggilan ekor, panggilan ekor memerlukan parameter yang diketahui pada saat panggilan dilakukan. Itu berarti jika salah satu parameter adalah panggilan ke fungsi itu sendiri, maka itu tidak dapat dikonversi menjadi loop, karena ini akan memerlukan bersarang sembarang dari loop yang tidak dapat diperluas pada waktu kompilasi.

  • C # tidak andal mengoptimalkan panggilan ekor. IL memiliki instruksi untuk melakukannya sehingga kompiler F # akan memancarkan, tetapi kompiler C # akan memancarkannya secara tidak konsisten, dan tergantung pada situasi JIT, JIT mungkin atau mungkin tidak melakukannya sama sekali. Semua indikasi adalah Anda tidak boleh bergantung pada panggilan ekor Anda yang dioptimalkan dalam C #, risiko meluap dalam melakukannya adalah signifikan dan nyata

Jimmy Hoffa
sumber
1
Apakah Anda yakin ini yang diminta OP? Seperti yang saya posting di bawah jawaban yang lain, hanya karena runtime tidak atau tidak mengkonsumsi ruang stack dengan cara tertentu, tidak berarti fungsinya tidak rekursif.
1
@MattFenwick itu sebenarnya adalah poin yang bagus, dalam hal ini tergantung, instruksi kompiler pemancar F # mempertahankan logika rekursif sepenuhnya, itu hanya menginstruksikan JIT untuk mengeksekusinya dengan cara mengganti-ruang-alih-alih-alih-ruang-stack- tumbuh, namun kompiler lain dapat dikompilasi secara harfiah menjadi sebuah loop. (Secara teknis JIT mengkompilasi ke loop atau mungkin bahkan tanpa loop mode jika loop total di depan)
Jimmy Hoffa