Mengapa ekor ini bersifat rekursif?

lihat kode Scala ini:

def rec(n: Int) {
  if (n > 1) {
    val d = n / 2
    rec(d)
//    if (d > 1)  // abort loop
      rec(n/d)
  }
}

Kode ini akan menghasilkan perulangan tanpa akhir. Karena optimasi rekursif ekor saya tidak mendapatkan StackOverflowError.

Didekompilasi dengan jad saya mendapatkan kode Java ini:

public void rec(int n)
{
    int d;
    for(; n > 1; n /= d)
    {
        int i = n;
        d = i / 2;
        rec(d);
    }
}

Di baris terakhir dari loop, metode memanggil dirinya sendiri oleh karena itu saya tidak mengerti posisi tail call. Adakah yang bisa menjelaskan hal ini?


scala tail-recursion
person kiritsuku    schedule 17.03.2011    source sumber
comment
Ini akan sangat membantu 1.cs. wayne.edu/~artem/main/teaching/csc3200ss2006/slides/ 2.stackoverflow.com/questions/105834/   -  person Dead Programmer    schedule 17.03.2011

Jawaban (2)


arrow_upward
9
arrow_downward

Tidak ada panggilan ekor dalam kasus rec(d). Untuk rec(N) (di mana N > 1) tumpukan tidak bertambah lagi setelah log2(N) panggilan (karena setelah itu n sama dengan 2 atau 3 selamanya, dan d adalah 1). Setelah itu hanya loop tak terbatas dengan panggilan rec(1) dalam yang segera kembali setiap saat. Itu sebabnya tidak ada stack overflow.

person hoha    schedule 17.03.2011

arrow_upward
3
arrow_downward

Dalam bentuk rekursif dari metode Anda, Anda memiliki dua panggilan rekursif. StackOverflowError disebabkan oleh yang terakhir.

Karena optimasi rekursi ekor, panggilan terakhir itu berubah menjadi loop (sementara panggilan pertama tetap bersifat rekursif), oleh karena itu Anda memiliki loop tak terbatas alih-alih rekursi tak terbatas, dan StackOverflowError tidak terjadi.

person axtavt    schedule 17.03.2011