Apa itu rekursi ekor?

Ketika mulai belajar lisp, saya menemukan istilah ekor-rekursif . Apa artinya sebenarnya?

Pertimbangkan fungsi sederhana yang menambahkan bilangan alami N 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 Anda menelepon recsum(5), inilah yang akan dinilai oleh penerjemah 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 penerjemah JavaScript mulai benar-benar melakukan pekerjaan menghitung jumlahnya.

Berikut ini adalah versi rekursif ekor 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 secara efektif akan menjadi 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 ekor-rekursif, dengan setiap evaluasi panggilan rekursif, yang running_totaldiperbarui.

Catatan: Jawaban asli menggunakan contoh-contoh dari Python. Ini telah diubah menjadi JavaScript, karena interpreter Python tidak mendukung optimasi panggilan ekor . Namun, sementara optimisasi panggilan ekor adalah bagian dari spesifikasi ECMAScript 2015 , sebagian besar penerjemah JavaScript tidak mendukungnya .

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

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

Konsekuensi dari hal ini adalah bahwa setelah Anda siap untuk melakukan langkah rekursif berikutnya, Anda tidak perlu bingkai tumpukan saat ini lagi. Ini memungkinkan beberapa optimasi. Bahkan, dengan kompiler yang ditulis dengan tepat, Anda seharusnya tidak pernah memiliki snicker stack overflow dengan panggilan rekursif ekor. Cukup gunakan kembali bingkai tumpukan saat ini untuk langkah rekursif berikutnya. Saya cukup yakin Lisp melakukan ini.

Poin penting adalah bahwa rekursi ekor pada dasarnya setara dengan perulangan. Ini bukan hanya masalah optimisasi kompiler, tetapi fakta mendasar tentang ekspresif. Ini berlaku dua arah: Anda dapat mengambil loop apa pun dari formulir

while(E) { S }; return Q

di mana Edan Qadalah ekspresi dan Smerupakan urutan pernyataan, dan mengubahnya menjadi fungsi rekursif ekor

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

Tentu saja, E, S, dan Qharus didefinisikan untuk menghitung beberapa nilai yang menarik atas beberapa variabel. Misalnya, fungsi pengulangan

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

setara dengan fungsi rekursif ekor

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 "pembungkus" dari fungsi rekursif ekor dengan fungsi dengan parameter lebih sedikit adalah idiom fungsional yang umum.)

Kutipan dari buku Programming in Lua ini menunjukkan bagaimana membuat rekursi ekor yang tepat (dalam Lua, tetapi juga berlaku untuk Lisp) dan mengapa itu lebih baik.

Sebuah panggilan ekor [rekursi ekor] adalah sejenis goto berpakaian sebagai panggilan. Panggilan ekor terjadi ketika suatu fungsi memanggil yang lain sebagai tindakan terakhirnya, sehingga tidak ada lagi yang bisa dilakukan. Misalnya, dalam kode berikut, panggilan ke gadalah panggilan ekor:

function f (x)
  return g(x)
end

Setelah fpanggilan g, tidak ada lagi yang bisa dilakukan. Dalam situasi seperti itu, program tidak perlu kembali ke fungsi panggilan ketika fungsi yang dipanggil berakhir. Oleh karena itu, setelah panggilan ekor, program tidak perlu menyimpan informasi tentang fungsi panggilan dalam tumpukan. ...

Karena panggilan ekor yang tepat tidak menggunakan ruang tumpukan, tidak ada batasan jumlah panggilan ekor "bersarang" yang dapat dilakukan oleh suatu program. Misalnya, kita dapat memanggil fungsi berikut dengan nomor berapapun sebagai argumen; itu tidak akan pernah meluap tumpukan:

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

... Seperti yang saya katakan sebelumnya, panggilan ekor adalah semacam kebohongan. Dengan demikian, aplikasi panggilan ekor yang tepat dan sangat berguna di Lua adalah untuk memprogram mesin negara. Aplikasi tersebut dapat mewakili setiap negara dengan fungsi; untuk mengubah status berarti pergi ke (atau memanggil) fungsi tertentu. Sebagai contoh, mari kita pertimbangkan permainan labirin sederhana. Labirin memiliki beberapa kamar, masing-masing dengan hingga empat pintu: utara, selatan, timur, dan barat. Pada setiap langkah, pengguna memasuki arah gerakan. Jika ada pintu ke arah itu, pengguna pergi ke kamar yang sesuai; jika tidak, program akan mencetak peringatan. Tujuannya adalah untuk pergi dari ruang awal ke ruang akhir.

Game ini adalah mesin khas negara, di mana ruang saat ini adalah negara. Kita dapat menerapkan labirin seperti itu dengan satu fungsi untuk setiap kamar. Kami menggunakan panggilan ekor untuk berpindah dari satu kamar ke kamar lainnya. 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 tahu, 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 dilakukan. Jika Anda memasukkan angka yang sangat tinggi, itu mungkin akan menyebabkan stack overflow.

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

Dengan rekursi ekor, tergantung pada bahasa, kompiler mungkin dapat menciutkan tumpukan ke satu entri, sehingga Anda menghemat ruang tumpukan ... Permintaan rekursif yang besar sebenarnya dapat menyebabkan stack overflow.

Pada dasarnya rekursi Tail dapat dioptimalkan menjadi iterasi.

File jargon mengatakan ini tentang definisi rekursi ekor:

rekursi ekor /n./

Jika Anda belum muak dengannya, lihat rekursi ekor.

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

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

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 dalam versi pertama bahwa panggilan rekursif ke fakta dimasukkan ke dalam ekspresi multiplikasi, dan oleh karena itu negara harus disimpan di tumpukan ketika melakukan panggilan rekursif. Dalam versi rekursif ekor tidak ada ekspresi S lain yang menunggu nilai panggilan rekursif, dan karena tidak ada pekerjaan lebih lanjut untuk dilakukan, negara tidak harus disimpan di stack. Sebagai aturan, fungsi rekursif skema menggunakan ruang stack konstan.

Tail recursion mengacu pada panggilan rekursif yang terakhir dalam instruksi logika terakhir dalam algoritma rekursif.

Biasanya dalam rekursi, Anda memiliki kasing dasar yang menghentikan panggilan rekursif dan mulai memunculkan tumpukan panggilan. Untuk menggunakan contoh klasik, meskipun lebih banyak C-ish dari Lisp, fungsi faktorial menggambarkan rekursi ekor. Panggilan rekursif terjadi setelah memeriksa kondisi casing dasar.

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

Panggilan awal ke faktorial akan menjadi factorial(n)tempat fac=1(nilai default) dan n adalah nomor yang faktorialnya harus dihitung.

Ini berarti bahwa daripada perlu mendorong penunjuk instruksi pada tumpukan, Anda cukup melompat ke atas fungsi rekursif dan melanjutkan eksekusi. Ini memungkinkan fungsi berulang tanpa batas tanpa menumpuk tumpukan.

Saya menulis posting blog tentang hal itu, yang memiliki contoh grafis seperti apa tampilan stack frame.

Berikut ini adalah cuplikan kode cepat yang membandingkan dua fungsi. Yang pertama adalah rekursi tradisional untuk menemukan faktorial dari angka yang diberikan. Yang kedua menggunakan rekursi ekor.

Sangat sederhana dan intuitif untuk dipahami.

Cara mudah untuk mengetahui apakah fungsi rekursif adalah tail recursive adalah jika mengembalikan nilai konkret dalam case dasar. Berarti itu tidak mengembalikan 1 atau benar atau semacamnya. Ini kemungkinan besar akan mengembalikan beberapa varian dari salah satu parameter metode.

Cara lain untuk mengetahui adalah jika panggilan rekursif bebas dari penambahan, aritmatika, modifikasi, dll ... Artinya tidak lain adalah panggilan rekursif murni.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Cara terbaik bagi saya untuk memahami tail call recursionadalah kasus rekursi khusus di mana panggilan terakhir (atau panggilan ekor) adalah fungsinya sendiri.

Membandingkan contoh yang diberikan dalam Python:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^ REKAMSI

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^ PERKEMBANGAN TAIL

Seperti yang Anda lihat di versi rekursif umum, panggilan terakhir di blok kode adalah x + recsum(x - 1). Jadi setelah memanggil recsummetode, ada operasi lain yaitu x + ...

Namun, dalam versi rekursif ekor, panggilan terakhir (atau panggilan ekor) dalam blok kode adalah tailrecsum(x - 1, running_total + x)yang berarti panggilan terakhir dilakukan pada metode itu sendiri dan tidak ada operasi setelah itu.

Poin ini penting karena rekursi ekor seperti yang terlihat di sini tidak membuat memori tumbuh karena ketika VM yang mendasarinya melihat suatu fungsi yang memanggil dirinya sendiri dalam posisi ekor (ekspresi terakhir yang dievaluasi dalam suatu fungsi), ia menghilangkan kerangka tumpukan saat ini, yang dikenal sebagai Tail Call Optimization (TCO).

EDIT

NB. Ingatlah bahwa contoh di atas ditulis dengan Python yang runtime-nya tidak mendukung TCO. Ini hanyalah contoh untuk menjelaskan maksudnya. TCO didukung dalam bahasa seperti Skema, Haskell dll

Di Jawa, berikut ini adalah kemungkinan implementasi berulang dari fungsi Fibonacci:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Bandingkan ini dengan penerapan rekursif standar:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Saya bukan programmer Lisp, tapi saya pikir ini akan membantu.

Pada dasarnya ini adalah gaya pemrograman sehingga panggilan rekursif adalah hal terakhir yang Anda lakukan.

Berikut adalah contoh Common Lisp yang melakukan faktorial menggunakan rekursi ekor. Karena sifat tanpa tumpukan, orang dapat melakukan perhitungan faktorial yang sangat besar ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

Dan untuk bersenang-senang Anda bisa mencoba (format nil "~R" (! 25))

Singkatnya, rekursi ekor memiliki panggilan rekursif sebagai pernyataan terakhir dalam fungsi sehingga tidak harus menunggu panggilan rekursif.

Jadi ini adalah rekursi ekor yaitu N (x - 1, p * x) adalah pernyataan terakhir dalam fungsi di mana kompiler cerdas untuk mengetahui bahwa ia dapat dioptimalkan untuk for-loop (faktorial). Parameter kedua p membawa nilai produk antara.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Ini adalah cara non-tail-rekursif untuk menulis fungsi faktorial di atas (walaupun beberapa kompiler C ++ mungkin dapat mengoptimalkannya).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

tapi ini bukan:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Saya memang menulis posting panjang berjudul " Memahami Rekursi Ekor - Visual Studio C ++ - Tampilan Perakitan "

di sini adalah versi Perl 5 dari tailrecsumfungsi yang disebutkan sebelumnya.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Ini adalah kutipan dari Struktur dan Interpretasi Program Komputer tentang rekursi ekor.

Dalam kontras iterasi dan rekursi, kita harus berhati-hati untuk tidak membingungkan gagasan tentang proses rekursif dengan gagasan prosedur rekursif. Ketika kami menggambarkan suatu prosedur sebagai rekursif, kami merujuk pada fakta sintaksis bahwa definisi prosedur merujuk (baik secara langsung atau tidak langsung) ke prosedur itu sendiri. Tetapi ketika kita menggambarkan suatu proses sebagai mengikuti pola yang, katakanlah, linier rekursif, kita berbicara tentang bagaimana proses berkembang, bukan tentang sintaks bagaimana sebuah prosedur ditulis. Tampaknya mengganggu bahwa kita merujuk pada prosedur rekursif seperti fakta-iter sebagai menghasilkan proses berulang. Namun, prosesnya benar-benar berulang: Keadaannya ditangkap sepenuhnya oleh tiga variabel keadaannya, dan seorang penerjemah perlu melacak hanya tiga variabel untuk menjalankan proses.

Salah satu alasan bahwa perbedaan antara proses dan prosedur dapat membingungkan adalah bahwa sebagian besar implementasi bahasa umum (termasuk Ada, Pascal, dan C) dirancang sedemikian rupa sehingga interpretasi dari setiap prosedur rekursif mengkonsumsi sejumlah memori yang tumbuh dengan sejumlah panggilan prosedur, bahkan ketika proses yang dijelaskan, pada prinsipnya, berulang. Sebagai konsekuensinya, bahasa-bahasa ini dapat menggambarkan proses berulang hanya dengan menggunakan “konstruksi pengulangan” tujuan khusus seperti do, repeat, hingga, for, and while. Implementasi Skema tidak berbagi cacat ini. Ini akan mengeksekusi proses berulang di ruang konstan, bahkan jika proses berulang dijelaskan oleh prosedur rekursif. Implementasi dengan properti ini disebut ekor-rekursif. Dengan implementasi ekor-rekursif, iterasi dapat diekspresikan menggunakan mekanisme panggilan prosedur biasa, sehingga konstruksi iterasi khusus hanya berguna sebagai gula sintaksis.

Fungsi rekursif adalah fungsi yang memanggil dengan sendirinya

Hal ini memungkinkan pemrogram untuk menulis program yang efisien menggunakan kode dalam jumlah minimal .

The downside adalah bahwa mereka dapat menyebabkan loop tak terbatas dan hasil tak terduga lainnya jika tidak ditulis dengan benar .

Saya akan menjelaskan fungsi Rekursif Sederhana dan fungsi Rekursif Ekor

Untuk menulis fungsi rekursif sederhana

1. Poin pertama yang harus dipertimbangkan adalah kapan Anda harus memutuskan untuk keluar dari loop yang merupakan loop if
2. Yang kedua adalah proses apa yang harus dilakukan jika kita adalah fungsi kita sendiri

Dari contoh yang diberikan:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Dari contoh di atas

if(n <=1)
     return 1;

Merupakan faktor penentu kapan harus keluar dari loop

else 
     return n * fact(n-1);

Apakah proses aktual yang harus dilakukan

Biarkan saya menyelesaikan tugas satu per satu untuk memudahkan pemahaman.

Mari kita lihat apa yang terjadi secara internal jika saya berlari fact(4)

1. Mengganti n = 4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

Ifloop gagal sehingga ia pergi ke elseloop sehingga ia kembali4 * fact(3)

2. Dalam memori tumpukan, kita miliki 4 * fact(3)

   Mengganti n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

Ifloop gagal sehingga ia pergi ke elseloop

jadi itu kembali 3 * fact(2)

Ingat kami memanggil `` `4 * fakta (3)` `

Output untuk fact(3) = 3 * fact(2)

Sejauh ini tumpukan telah 4 * fact(3) = 4 * 3 * fact(2)

3. Dalam memori tumpukan, kita miliki 4 * 3 * fact(2)

   Mengganti n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

Ifloop gagal sehingga ia pergi ke elseloop

jadi itu kembali 2 * fact(1)

Ingat kami menelepon 4 * 3 * fact(2)

Output untuk fact(2) = 2 * fact(1)

Sejauh ini tumpukan telah 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. Dalam memori tumpukan, kita miliki 4 * 3 * 2 * fact(1)

   Mengganti n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If lingkaran itu benar

jadi itu kembali 1

Ingat kami menelepon 4 * 3 * 2 * fact(1)

Output untuk fact(1) = 1

Sejauh ini tumpukan telah 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Akhirnya, hasil dari fakta (4) = 4 * 3 * 2 * 1 = 24

The Tail Rekursi akan

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. Mengganti n = 4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

Ifloop gagal sehingga ia pergi ke elseloop sehingga ia kembalifact(3, 4)

2. Dalam memori tumpukan, kita miliki fact(3, 4)

   Mengganti n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

Ifloop gagal sehingga ia pergi ke elseloop

jadi itu kembali fact(2, 12)

2. Dalam memori tumpukan, kita miliki fact(2, 12)

   Mengganti n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

Ifloop gagal sehingga ia pergi ke elseloop

jadi itu kembali fact(1, 24)

3. Dalam memori tumpukan, kita miliki fact(1, 24)

   Mengganti n = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If lingkaran itu benar

jadi itu kembali running_total

Output untuk running_total = 24

Akhirnya, hasil dari fakta (4,1) = 24

Rekursi ekor adalah kehidupan yang Anda jalani saat ini. Anda terus-menerus mendaur ulang bingkai tumpukan yang sama, berulang-ulang, karena tidak ada alasan atau cara untuk kembali ke bingkai "sebelumnya". Masa lalu sudah lewat dan selesai sehingga bisa dibuang. Anda mendapatkan satu bingkai, selamanya bergerak ke masa depan, sampai proses Anda pasti mati.

_{Analogi ini rusak ketika Anda mempertimbangkan beberapa proses mungkin menggunakan frame tambahan tetapi masih dianggap ekor rekursif jika tumpukan tidak tumbuh tanpa batas.}

Rekursi ekor adalah fungsi rekursif di mana fungsi memanggil dirinya sendiri di akhir ("ekor") dari fungsi di mana tidak ada perhitungan yang dilakukan setelah kembalinya panggilan rekursif. Banyak kompiler mengoptimalkan untuk mengubah panggilan rekursif menjadi ekor rekursif atau panggilan berulang.

Pertimbangkan masalah menghitung faktorial suatu angka.

Pendekatan langsung adalah:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Misalkan Anda memanggil faktorial (4). Pohon rekursi adalah:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

Kedalaman rekursi maksimum dalam kasus di atas adalah O (n).

Namun, perhatikan contoh berikut:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Rekursi pohon untuk factTail (4) adalah:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Di sini juga, kedalaman rekursi maksimum adalah O (n) tetapi tidak ada panggilan yang menambahkan variabel tambahan ke stack. Karenanya kompiler dapat menghapus stack.

Rekursi Ekor cukup cepat dibandingkan dengan rekursi normal. Itu cepat karena output dari panggilan leluhur tidak akan ditulis dalam tumpukan untuk melacak. Namun dalam rekursi normal semua leluhur memanggil output yang ditulis dalam stack untuk menjaga track.

SEBUAH ekor rekursif fungsi adalah fungsi rekursif di mana operasi terakhir yang dilakukannya sebelum kembali yaitu membuat panggilan fungsi rekursif. Artinya, nilai kembali panggilan fungsi rekursif segera dikembalikan. Misalnya, kode Anda akan terlihat seperti ini:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Kompiler dan penerjemah yang mengimplementasikan optimisasi panggilan tail atau eliminasi panggilan ekor dapat mengoptimalkan kode rekursif untuk mencegah tumpukan berlebih. Jika kompiler atau juru bahasa Anda tidak menerapkan pengoptimalan panggilan ekor (seperti juru bahasa CPython), tidak ada manfaat tambahan untuk menulis kode Anda dengan cara ini.

Sebagai contoh, ini adalah fungsi faktorial rekursif standar dalam Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

Dan ini adalah versi rekursif panggilan ekor dari fungsi faktorial:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Perhatikan bahwa meskipun ini adalah kode Python, juru bahasa CPython tidak melakukan optimasi panggilan ekor, jadi mengatur kode Anda seperti ini tidak memberikan manfaat runtime.)

Anda mungkin harus membuat kode Anda sedikit lebih tidak dapat dibaca untuk menggunakan optimasi panggilan ekor, seperti yang ditunjukkan dalam contoh faktorial. (Misalnya, kasus dasar sekarang agak tidak intuitif, danaccumulator parameternya secara efektif digunakan sebagai semacam variabel global.)

Tetapi manfaat dari optimasi panggilan ekor adalah mencegah kesalahan stack overflow. (Saya akan perhatikan bahwa Anda bisa mendapatkan manfaat yang sama dengan menggunakan algoritma iteratif alih-alih yang rekursif.)

Tumpukan melimpah disebabkan ketika tumpukan panggilan memiliki terlalu banyak objek bingkai didorong ke. Objek bingkai didorong ke tumpukan panggilan saat fungsi dipanggil, dan keluar dari tumpukan panggilan saat fungsi kembali. Objek bingkai berisi info seperti variabel lokal dan baris kode apa yang akan kembali ketika fungsi kembali.

Jika fungsi rekursif Anda membuat terlalu banyak panggilan rekursif tanpa kembali, tumpukan panggilan dapat melebihi batas objek bingkainya. (Jumlahnya bervariasi berdasarkan platform; dalam Python itu adalah 1000 objek frame secara default.) Ini menyebabkan stack overflow kesalahan . (Hei, dari situlah nama situs web ini berasal!)

Namun, jika hal terakhir yang dilakukan fungsi rekursif Anda adalah membuat panggilan rekursif dan mengembalikan nilai pengembaliannya, maka tidak ada alasan yang diperlukan untuk menjaga objek frame saat ini tetap berada di tumpukan panggilan. Lagi pula, jika tidak ada kode setelah pemanggilan fungsi rekursif, tidak ada alasan untuk bergantung pada variabel lokal objek frame saat ini. Jadi kita bisa menyingkirkan objek frame saat ini segera daripada menyimpannya di tumpukan panggilan. Hasil akhir dari ini adalah bahwa tumpukan panggilan Anda tidak tumbuh dalam ukuran, dan dengan demikian tidak dapat menumpuk overflow.

Compiler atau interpreter harus memiliki optimasi panggilan tail sebagai fitur agar dapat mengenali kapan optimasi panggilan tail dapat diterapkan. Bahkan kemudian, Anda mungkin telah mengatur ulang kode dalam fungsi rekursif Anda untuk memanfaatkan pengoptimalan panggilan ekor, dan terserah Anda jika potensi penurunan dalam keterbacaan ini layak dioptimalkan.

Untuk memahami beberapa perbedaan inti antara rekursi panggilan-ekor dan rekursi non-panggilan-ekor, kita dapat menjelajahi implementasi .NET dari teknik-teknik ini.

Berikut ini adalah artikel dengan beberapa contoh di C #, F #, dan C ++ \ CLI: Petualangan di Ekor Rekursi dalam C #, F #, dan C ++ \ CLI .

C # tidak mengoptimalkan untuk rekursi panggilan balik sedangkan F # tidak.

Perbedaan prinsip melibatkan loop vs Lambda calculus. C # dirancang dengan mempertimbangkan loop sedangkan F # dibangun dari prinsip-prinsip kalkulus Lambda. Untuk buku yang sangat bagus (dan gratis) tentang prinsip-prinsip kalkulus Lambda, lihat Struktur dan Interpretasi Program Komputer, oleh Abelson, Sussman, dan Sussman .

Mengenai panggilan ekor di F #, untuk artikel pengantar yang sangat bagus, lihat Pengenalan terperinci untuk Panggilan Panggilan di F # . Akhirnya, berikut adalah artikel yang mencakup perbedaan antara rekursi non-ekor dan rekursi ekor-panggilan (dalam F #): Rekursi ekor-vs rekursi non-ekor dalam F tajam .

Jika Anda ingin membaca tentang beberapa perbedaan desain rekursi panggilan balik antara C # dan F #, lihat Menghasilkan Kode Panggilan Ekor di C # dan F # .

Jika Anda cukup peduli untuk ingin tahu kondisi apa yang mencegah kompiler C # melakukan optimisasi panggilan-ekor, lihat artikel ini: kondisi panggilan ekor JIT CLR .

Ada dua jenis dasar rekursi: rekursi kepala dan rekursi ekor.

Dalam rekursi kepala , suatu fungsi membuat panggilan rekursif dan kemudian melakukan beberapa perhitungan lagi, mungkin menggunakan hasil dari panggilan rekursif, misalnya.

Dalam fungsi rekursif ekor , semua perhitungan terjadi terlebih dahulu dan panggilan rekursif adalah hal terakhir yang terjadi.

Diambil dari ini posting mengagumkan super. Silakan mempertimbangkan untuk membacanya.

Rekursi berarti suatu fungsi yang memanggil dirinya sendiri. Sebagai contoh:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Ekor-Rekursi berarti rekursi yang menyimpulkan fungsi:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Lihat, fungsi terakhir yang tidak berakhir (prosedur, dalam jargon Skema) lakukan adalah memanggil dirinya sendiri. Contoh (lebih bermanfaat) lainnya adalah:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

Dalam prosedur helper, hal TERAKHIR yang dilakukannya jika kiri bukan nol adalah memanggil dirinya sendiri (SETELAH kontra sesuatu dan melakukan sesuatu). Ini pada dasarnya adalah bagaimana Anda memetakan daftar.

Ekor-rekursi memiliki keuntungan besar sehingga interpreter (atau kompiler, bergantung pada bahasa dan vendor) dapat mengoptimalkannya, dan mengubahnya menjadi sesuatu yang setara dengan loop sementara. Faktanya, dalam tradisi Skema, sebagian besar loop "untuk" dan "sementara" dilakukan dengan cara rekursi ekor (tidak ada untuk dan sementara, sejauh yang saya tahu).

Pertanyaan ini memiliki banyak jawaban yang bagus ... tapi saya tidak bisa tidak ikut campur dengan cara lain untuk mendefinisikan "rekursi ekor", atau setidaknya "rekursi ekor yang tepat." Yaitu: haruskah seseorang melihatnya sebagai properti ekspresi tertentu dalam suatu program? Atau haruskah orang melihatnya sebagai properti dari implementasi bahasa pemrograman ?

Untuk lebih lanjut tentang tampilan terakhir, ada kertas klasik oleh Will Clinger, "Rekursi Ekor yang Tepat dan Efisiensi Ruang" (PLDI 1998), yang mendefinisikan "rekursi ekor yang tepat" sebagai properti dari implementasi bahasa pemrograman. Definisi ini dibangun untuk memungkinkan seseorang mengabaikan detail implementasi (seperti apakah tumpukan panggilan benar-benar diwakili melalui tumpukan runtime atau melalui daftar bingkai yang ditautkan oleh tumpukan yang dialokasikan).

Untuk mencapai hal ini, ia menggunakan analisis asimptotik: bukan waktu pelaksanaan program seperti yang biasa dilihat, melainkan penggunaan ruang program . Dengan cara ini, penggunaan ruang dari daftar tertaut yang dialokasikan berdasarkan tumpukan vs tumpukan panggilan runtime akhirnya menjadi setara secara asimptotik; sehingga orang dapat mengabaikan bahwa detail implementasi bahasa pemrograman (detail yang tentu saja sangat penting dalam praktiknya, tetapi dapat sedikit memperkeruh perairan ketika seseorang mencoba untuk menentukan apakah implementasi yang diberikan memenuhi persyaratan untuk menjadi "properti ekor rekursif" )

Makalah ini layak dipelajari dengan cermat karena sejumlah alasan:

• Ini memberikan definisi induktif dari ekspresi ekor dan panggilan ekor suatu program. (Definisi seperti itu, dan mengapa panggilan seperti itu penting, tampaknya menjadi subjek dari sebagian besar jawaban lain yang diberikan di sini.)

  Berikut adalah definisi-definisi itu, hanya untuk memberikan rasa pada teks:

  Definisi 1 The ekspresi ekor dari program yang ditulis dalam inti Skema didefinisikan secara induktif sebagai berikut.

  1. Tubuh ekspresi lambda adalah ekspresi ekor
  2. Jika (if E0 E1 E2)adalah ekspresi ekor, maka kedua E1dan E2adalah ekspresi ekor.
  3. Tidak ada yang lain adalah ekspresi ekor.

  Definisi 2 Sebuah panggilan ekor adalah ekspresi ekor yang merupakan panggilan prosedur.

(panggilan rekursif ekor, atau seperti yang dikatakan surat kabar, "panggilan ekor sendiri" adalah kasus khusus dari panggilan ekor di mana prosedur dipanggil sendiri.)

• Ini memberikan definisi formal untuk enam "mesin" yang berbeda untuk mengevaluasi Skema Inti, di mana setiap mesin memiliki perilaku yang dapat diamati yang sama kecuali untuk kelas kompleksitas ruang asimptotik yang dimiliki masing-masing.

  Sebagai contoh, setelah memberikan definisi untuk mesin dengan masing-masing, 1. manajemen memori berbasis stack, 2. pengumpulan sampah tetapi tidak ada panggilan ekor, 3. pengumpulan sampah dan panggilan ekor, kertas terus maju dengan strategi manajemen penyimpanan yang lebih maju, seperti 4. "rekursi ekor evlis", di mana lingkungan tidak perlu dipertahankan sepanjang evaluasi argumen sub-ekspresi terakhir dalam panggilan ekor, 5. mengurangi lingkungan penutupan menjadi hanya variabel bebas dari penutupan itu, dan 6. apa yang disebut semantik "ruang aman" sebagaimana didefinisikan oleh Appel dan Shao .

• Untuk membuktikan bahwa mesin tersebut sebenarnya termasuk ke dalam enam kelas kompleksitas ruang yang berbeda, makalah tersebut, untuk setiap pasangan mesin yang sedang dibandingkan, memberikan contoh konkret dari program yang akan mengekspos ruang ledakan asimptotik pada satu mesin tetapi tidak yang lain.

(Membaca jawaban saya sekarang, saya tidak yakin apakah saya berhasil menangkap poin-poin penting dari kertas Clinger . Tetapi, sayangnya, saya tidak dapat mencurahkan lebih banyak waktu untuk mengembangkan jawaban ini sekarang.)

Banyak orang sudah menjelaskan rekursi di sini. Saya ingin mengutip beberapa pemikiran tentang beberapa keuntungan yang rekursi berikan dari buku "Concurrency in. NET, pola modern pemrograman paralel dan paralel" oleh Riccardo Terrell:

“Rekursi fungsional adalah cara alami untuk beralih di FP karena menghindari mutasi negara. Selama setiap iterasi, nilai baru dilewatkan ke konstruktor lingkaran alih-alih diperbarui (dimutasi). Selain itu, fungsi rekursif dapat dikomposisikan, membuat program Anda lebih modular, serta memperkenalkan peluang untuk mengeksploitasi paralelisasi. "

Berikut juga beberapa catatan menarik dari buku yang sama tentang rekursi ekor:

Tail-call recursion adalah teknik yang mengubah fungsi rekursif reguler menjadi versi yang dioptimalkan yang dapat menangani input besar tanpa risiko dan efek samping.

CATATAN Alasan utama untuk panggilan ekor sebagai optimisasi adalah untuk meningkatkan lokalitas data, penggunaan memori, dan penggunaan cache. Dengan melakukan panggilan ekor, callee menggunakan ruang tumpukan yang sama dengan penelepon. Ini mengurangi tekanan memori. Ini sedikit meningkatkan cache karena memori yang sama digunakan kembali untuk penelepon berikutnya dan dapat tetap dalam cache, daripada mengusir garis cache yang lebih tua untuk memberikan ruang bagi baris cache yang baru.