Perbedaan antara Ekor-Rekursi dan rekursi struktural

Rekursi struktural: panggilan rekursif dilakukan dengan argumen yang lebih kecil secara struktural .
Tail recursion: panggilan rekursif adalah hal terakhir yang terjadi.

Tidak ada persyaratan bahwa rekursi ekor harus dipanggil pada argumen yang lebih kecil. Bahkan, cukup sering fungsi rekursif ekor dirancang untuk berulang selamanya. Sebagai contoh, ini adalah rekursi ekor sepele (tidak terlalu berguna, tetapi rekursi ekor):

def f(x):
   return f(x+1)

Kami sebenarnya harus lebih berhati-hati. Mungkin ada beberapa panggilan rekursif dalam suatu fungsi, dan tidak semua panggilan harus rekursif:

def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

Seseorang berbicara tentang panggilan rekursif ekor . Suatu fungsi yang panggilan rekursifnya adalah semua ekor-rekursif kemudian disebut fungsi ekor-rekursif.

Andrej Bauer
sumber

Mari kita lanjutkan diskusi ini dalam obrolan .

Davislor

Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .

Rekursi ekor adalah kasus rekursi struktural yang sangat sederhana, di mana struktur yang dimaksud adalah daftar terkait . Dalam bahasa yang mungkin Anda gunakan terutama, daftar ini mungkin tidak secara harfiah dalam kode; alih-alih, ini adalah "daftar panggilan ke fungsi" konseptual, sebuah konsep yang mungkin tidak dapat diungkapkan dengan tertulis menggunakan bahasa itu. Dalam Haskell (bahasa saya), setiap pemanggilan fungsi ekor-rekursif sebenarnya dapat diganti dengan mengurutkan tindakan pada daftar literal yang unsur-unsurnya secara harfiah adalah "panggilan ke fungsi", tetapi ini mungkin merupakan hal bahasa fungsional.

Rekursi struktural adalah cara beroperasi pada objek yang didefinisikan sebagai komposit dari objek lain (mungkin komposit). Sebagai contoh, pohon biner adalah objek yang berisi referensi ke dua pohon biner, atau kosong (dengan demikian, itu adalah objek yang didefinisikan secara rekursif ). Lebih sedikit referensi diri, sepasang (t1, t2) yang mengandung dua nilai dari beberapa tipe t1 dan t2 mengakui rekursi struktural, meskipun t1 dan t2 tidak perlu juga berpasangan. Rekursi ini berbentuk

aksi pada pasangan = kombinasi hasil tindakan lain pada setiap elemen

yang kedengarannya tidak terlalu dalam.

Sering terjadi bahwa rekursi struktural tidak dapat rekursif ekor, meskipun segala jenis rekursi dapat ditulis ulang sebagai rekursi ekor (bukti: jika Anda menjalankan rekursi asli, tindakan diselesaikan dalam urutan tertentu; oleh karena itu, rekursi tersebut setara dengan melakukan urutan tindakan tertentu, yang seperti yang saya bahas sebelumnya, adalah rekursi ekor).

Entah pohon biner atau pasangan contoh di atas menunjukkan ini: namun Anda mengatur panggilan rekursif pada sub-objek, hanya satu dari mereka yang bisa menjadi tindakan terakhir; mungkin tidak ada yang, jika hasilnya digabungkan dalam beberapa cara (katakanlah, penambahan). Seperti yang dikatakan Andrej Bauer dalam jawabannya, ini dapat terjadi bahkan dengan hanya satu panggilan rekursif, selama hasilnya diubah. Dengan kata lain, untuk setiap jenis objek selain yang secara efektif terkait daftar (hanya satu sub-objek semua jalan ke bawah), rekursi struktural bukanlah rekursi ekor.

Ryan Reich
sumber

Adalah salah bahwa rekursi ekor hanya tentang daftar, yang dibayangkan atau nyata. Sangat mungkin untuk memiliki rekursi ekor di atas pohon biner, misalnya. Saya bisa melihat mengapa seseorang mengira itu karena sisa daftar itu adalah "ekornya".

Andrej Bauer

@AndrejBauer Saya akan merasa malu tentang hal ini ketika saya mengerti persis apa yang salah. Tampaknya tautologis bahwa rekursi ekor dari bentuk f x = (stuff defining x'); f x'ini sama dengan urutan simpul dalam daftar tertaut yang didefinisikan seperti l = modify f : l(dalam gaya negara-monad Haskell). Itu bukan hanya kesamaan terminologis bagi saya. Adapun rekursi ekor di atas pohon biner, dapatkah Anda menguraikannya? Saya hanya bisa memikirkan fakta linierisasi dari paragraf kedua-terakhir saya.

Ryan Reich

Tidak semua panggilan berulang rekursif adalah dari bentuk itu. Misalnya, mungkin ada beberapa panggilan rekursif ekor di cabang yang berbeda (laporan kasus, atau semacamnya). Lebih alami untuk memikirkan mereka yang memilih jalan melalui pohon . Perhatikan juga bahwa panggilan tersebut bersifat ekor rekursif (atau tidak), sehingga Anda bisa memiliki di f (f x)mana panggilan luar fadalah ekor-rekursif. Bagaimana hal itu sesuai dengan pandangan bahwa ini semua tentang daftar? Berikut contoh lain: f : (Int -> Int) -> (Int -> Int)dengan f g 0 = g 42dan f g (n + 1) = f (f . g) n. Kemungkinannya tidak terbatas, dan beberapa berguna.

Andrej Bauer

@AndrejBauer Pertanyaannya adalah tentang rekursi ekor bukan hanya panggilan ekor , jadi saya tidak akan mempertimbangkan yang f (f x)berlaku: dalam evaluasi f terluar, yang dalam bukan panggilan ekor (kecuali f adalah identitas). Jika-laporan dapat sepele ditulis ulang untuk tidak cabang di panggilan ekor: if (c) then f a else f b == let x = if (c) then a else b in f x. Contoh terakhir tidak valid karena f . gtidak mengetik centang; Meski begitu, itu masih bukan rekursi ekor: f g = \n -> if n == 0 then g 42 else f (f . g) (n - 1)bukan panggilan untuk f, tetapi lambda yang benar-benar berbeda. (berikutnya)

Ryan Reich

Aku benar-benar mengatakan contoh yang dari rekursi ekor saling , yaitu f g = h where { h 0 = g 42; h n = f (f . g) (n - 1) }, tetapi jika Anda membawa itu ke dalam diskusi, maka setiap fungsi rekursif, ekor atau tidak, dapat diterima dan istilah menjadi tidak berarti.

Ryan Reich

Perbedaan antara Ekor-Rekursi dan rekursi struktural

Jawaban: