Pertanyaan Apa itu rekursi ekor?


Sementara mulai belajar cadel, saya telah menemukan istilah itu tail-rekursif. Apa artinya sebenarnya?


1294
2017-08-31 18:21


asal


Jawaban:


Pertimbangkan fungsi sederhana yang menambahkan N bilangan bulat pertama. (misalnya. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Berikut ini adalah implementasi JavaScript sederhana yang menggunakan rekursi:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Jika kamu menelepon recsum(5), inilah yang akan dievaluasi oleh interpreter JavaScript:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Perhatikan bagaimana setiap panggilan rekursif harus diselesaikan sebelum juru bahasa JavaScript mulai benar-benar melakukan pekerjaan menghitung jumlah tersebut.

Inilah versi ekor-rekursif dari fungsi yang sama:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Inilah urutan kejadian yang akan terjadi jika Anda menelepon tailrecsum(5), (yang akan efektif tailrecsum(5, 0), karena argumen kedua default).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

Dalam kasus tail-recursive, dengan setiap evaluasi panggilan rekursif, yang running_total diperbarui.

Catatan: Jawaban asli menggunakan contoh dari Python. Ini telah diubah menjadi JavaScript, karena penafsir JavaScript modern mendukung optimasi panggilan ekor tetapi juru bahasa Python tidak.


1292
2017-08-29 03:57



Di rekursi tradisional, model yang khas adalah Anda melakukan panggilan rekursif terlebih dahulu, dan kemudian Anda mengambil nilai kembalian dari panggilan rekursif dan menghitung hasilnya. Dengan cara ini, Anda tidak mendapatkan hasil perhitungan sampai Anda kembali dari setiap panggilan rekursif.

Di rekursi ekor, Anda melakukan perhitungan pertama, dan kemudian Anda menjalankan panggilan rekursif, meneruskan hasil langkah Anda saat ini ke langkah rekursif berikutnya. Ini menghasilkan pernyataan terakhir dalam bentuk (return (recursive-function params)). Pada dasarnya, nilai kembalian dari setiap langkah rekursif yang diberikan adalah sama dengan nilai kembalian dari panggilan rekursif berikutnya.

Konsekuensi dari ini adalah bahwa begitu Anda siap untuk melakukan langkah rekursif berikutnya, Anda tidak perlu tumpukan frame saat ini lagi. Ini memungkinkan beberapa optimasi. Bahkan, dengan compiler yang ditulis dengan tepat, Anda seharusnya tidak pernah memiliki stack overflow kekek dengan panggilan rekursif ekor. Cukup gunakan kembali tumpukan frame saat ini untuk langkah rekursif berikutnya. Saya sangat yakin Lisp melakukan ini.


546
2017-08-31 17:29



Poin penting adalah bahwa rekursi ekor pada dasarnya setara dengan perulangan. Ini bukan hanya masalah optimasi kompilator, tetapi fakta mendasar tentang ekspresif. Ini berlaku dua cara: Anda dapat mengambil setiap loop dari formulir

while(E) { S }; return Q

dimana E dan Q adalah ekspresi dan S adalah urutan pernyataan, dan mengubahnya menjadi fungsi rekursif ekor

f() = if E then { S; return f() } else { return Q }

Tentu saja, E, S, dan Q harus didefinisikan untuk menghitung beberapa nilai menarik atas beberapa variabel. Misalnya, fungsi perulangan

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

setara dengan fungsi tail-recursive (s)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Ini "membungkus" dari fungsi ekor-rekursif dengan fungsi dengan lebih sedikit parameter adalah idiom fungsional umum.)


165
2017-08-29 16:03



Ini kutipan dari buku itu Pemrograman di Lua pertunjukan bagaimana membuat rekahan ekor yang tepat (di Lua, tetapi harus berlaku untuk Lisp juga) dan mengapa itu lebih baik.

SEBUAH panggilan ekor [Ekstraksi ekor] adalah semacam goto berpakaian   sebagai panggilan. Panggilan ekor terjadi saat a   fungsi memanggil yang lain sebagai yang terakhir   tindakan, jadi tidak ada yang bisa dilakukan.   Misalnya, dalam kode berikut,   panggilan ke g adalah panggilan ekor:

function f (x)
  return g(x)
end

Setelah f panggilan g, tidak ada yang lain   melakukan. Dalam situasi seperti itu, program   tidak perlu kembali ke panggilan   berfungsi saat fungsi yang dipanggil   berakhir. Karena itu, setelah panggilan ekor,   program tidak perlu menyimpannya   informasi tentang fungsi panggilan   di dalam tumpukan. ...

Karena panggilan ekor yang tepat tidak menggunakan   ruang stack, tidak ada batasan pada   jumlah panggilan ekor "bertingkat" yang a   program bisa dibuat. Misalnya, kita bisa   panggil fungsi berikut dengan apa saja   angka sebagai argumen; itu tidak akan pernah terjadi   meluap tumpukan:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Seperti yang saya katakan sebelumnya, panggilan ekor adalah a   semacam goto. Dengan demikian, itu cukup bermanfaat   aplikasi panggilan ekor yang tepat di   Lua adalah untuk memprogram mesin negara.   Aplikasi semacam itu dapat mewakili masing-masing   menyatakan berdasarkan fungsi; untuk mengubah negara   adalah pergi ke (atau memanggil) spesifik   fungsi. Sebagai contoh, mari kita   pertimbangkan permainan labirin sederhana. Labirin   memiliki beberapa kamar, masing-masing hingga   empat pintu: utara, selatan, timur, dan   Barat. Pada setiap langkah, pengguna memasukkan a   arah gerakan. Jika ada pintu   ke arah itu, pengguna pergi ke   ruang yang sesuai; sebaliknya, the   program mencetak peringatan. Tujuannya adalah   untuk pergi dari ruang awal ke final   kamar.

Game ini adalah mesin negara yang khas,   di mana ruangan saat ini adalah negara.   Kita bisa mengimplementasikan labirin semacam itu dengan satu   berfungsi untuk setiap kamar. Kami menggunakan ekor   panggilan untuk berpindah dari satu kamar ke   lain. Sebuah labirin kecil dengan empat kamar   bisa terlihat seperti ini:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Jadi Anda lihat, ketika Anda membuat panggilan rekursif seperti:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Ini bukan ekor rekursif karena Anda masih memiliki hal-hal yang harus dilakukan (tambahkan 1) dalam fungsi itu setelah panggilan rekursif dibuat. Jika Anda memasukkan angka yang sangat tinggi mungkin akan menyebabkan tumpukan tumpahan.


110
2017-08-29 03:55



Menggunakan rekursi biasa, setiap panggilan rekursif mendorong entri lain ke tumpukan panggilan. Ketika rekursi selesai, aplikasi kemudian harus pop setiap entri dari semua jalan kembali ke bawah.

Dengan rekursi ekor, kompilator dapat meruntuhkan tumpukan ke satu entri, jadi Anda menghemat ruang tumpukan ... Kueri rekursif besar benar-benar dapat menyebabkan tumpukan kelebihan.

Pada dasarnya, rekursi ekor dapat dioptimalkan ke dalam iterasi.


57
2017-08-29 03:57



Daripada menjelaskannya dengan kata-kata, inilah contohnya. Ini adalah versi Skema dari fungsi faktorial:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Berikut ini adalah versi faktorial yang bersifat rekursif-ekor:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Anda akan melihat di versi pertama bahwa panggilan rekursif untuk fakta dimasukkan ke dalam ekspresi perkalian, dan karena itu negara harus disimpan pada tumpukan ketika membuat panggilan rekursif. Dalam versi tail-recursive tidak ada S-ekspresi lain yang menunggu nilai panggilan rekursif, dan karena tidak ada pekerjaan lebih lanjut yang harus dilakukan, negara tidak harus disimpan di stack. Sebagai aturan, Skema fungsi rekursif-skema menggunakan ruang stack konstan.


56
2017-08-29 07:21



File jargon memiliki ini untuk mengatakan tentang definisi rekursi ekor:

rekursi ekor /n./

Jika Anda belum bosan, lihat rekursi ekor.


52
2017-08-29 03:57



Ekor rekursi mengacu pada panggilan rekursif yang terakhir dalam instruksi logika terakhir dalam algoritma rekursif.

Biasanya dalam rekursi Anda memiliki kotak dasar yang menghentikan panggilan rekursif dan mulai memanggil tumpukan panggilan. Untuk menggunakan contoh klasik, meskipun lebih banyak C-ish daripada Lisp, fungsi faktorial menggambarkan rekursi ekor. Panggilan rekursif terjadi setelah memeriksa kondisi base-case.

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Catatan, panggilan awal untuk faktorial harus faktorial (n, 1) di mana n adalah nomor yang faktorial harus dihitung.


23
2017-08-31 23:52



Ini berarti bahwa daripada perlu mendorong pointer instruksi pada stack, Anda dapat langsung melompat ke atas fungsi rekursif dan melanjutkan eksekusi. Hal ini memungkinkan fungsi-fungsi untuk rekursi tanpa batas tanpa meluap-luap.

Saya menulis a blog posting pada subjek, yang memiliki contoh grafis dari apa yang tampak seperti tumpukan frame.


20
2017-10-14 21:20