Scala for Backend Engineering & Functional Programming · Pelajaran

Anotasi tailrec

Optimasi terjamin.

Anotasi tailrec adalah pelajaran Scala for Backend Engineering & Functional Programming gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Scala for Backend Engineering & Functional Programming, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Scala for Backend Engineering & Functional Programming mencakup 4 pelajaran total.

Apa Itu Rekursi Ekor?

Pemanggilan rekursif berada dalam posisi ekor ketika pemanggilan tersebut merupakan tindakan terakhir fungsi. Fungsi rekursif-ekor dapat dioptimalkan menjadi perulangan yang menggunakan kembali satu bingkai tumpukan, sehingga tidak pernah mengalami luapan.

Posisi Ekor

Dalam n * factorial(n-1), pemanggilan rekursif bukan tindakan terakhir: perkalian berlangsung setelah pemanggilan mengembalikan hasil. Dalam gcd(b, a % b), pemanggilan tersebut merupakan tindakan terakhir. Hanya yang kedua yang bersifat rekursif-ekor.

Anotasi @tailrec

Impor scala.annotation.tailrec dan anotasi suatu metode. Kompiler kemudian memverifikasi bahwa pemanggilan tersebut benar-benar berada dalam posisi ekor dan menerapkan optimasi. Jika tidak, kompilasi gagal.

import scala.annotation.tailrec

object Main {
  @tailrec
  def countdown(n: Int): Unit = {
    if (n >= 0) {
      println(n)
      countdown(n - 1)
    }
  }

  def main(args: Array[String]): Unit = countdown(3)
}

Optimasi yang Terjamin

Manfaat utama @tailrec adalah jaminan saat kompilasi. Anda segera diberi tahu jika fungsi Anda tidak aman terhadap tumpukan, alih-alih mengetahuinya melalui kerusakan saat runtime pada masukan besar.

gcd Rekursif-Ekor

Algoritma Euclid sudah bersifat rekursif-ekor: pemanggilan rekursif merupakan seluruh hasil isi fungsi. Menambahkan anotasi mengonfirmasi hal ini.

import scala.annotation.tailrec

object Main {
  @tailrec
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(1071, 462))
  }
}

Hal yang Mengeluarkan Pemanggilan dari Posisi Ekor

Pola umum yang mengeluarkan pemanggilan dari posisi ekor:

Melakukan aritmetika pada hasilnya: n + f(...).
Membungkusnya dalam konstruktor: x :: f(...).
Menggunakan hasilnya dalam blok try.

Contoh Non-Ekor

Jumlah ini bukan rekursif-ekor karena penjumlahan membungkus pemanggilan. Menambahkan anotasi @tailrec akan menyebabkan kesalahan kompilasi. (Ditampilkan tanpa anotasi agar dapat dijalankan.)

object Main {
  def sum(n: Int): Int =
    if (n == 0) 0
    else n + sum(n - 1)

  def main(args: Array[String]): Unit = {
    println(sum(100))
  }
}

Mengapa Tidak Dapat Dioptimalkan

Karena n + sum(n - 1) harus mengingat n untuk menyelesaikan penjumlahan setelah pemanggilan selesai, setiap tingkat memerlukan bingkai tumpukannya sendiri. Kompiler tidak dapat meringkasnya menjadi perulangan, sehingga fungsi ini bukan rekursif-ekor.

Perulangan Rekursif-Ekor Besar

Jumlah rekursif-ekor yang menggunakan akumulator dapat berjalan pada masukan yang sangat besar tanpa luapan, karena menggunakan kembali satu bingkai.

import scala.annotation.tailrec

object Main {
  @tailrec
  def sumTo(n: Int, acc: Long = 0): Long =
    if (n == 0) acc else sumTo(n - 1, acc + n)

  def main(args: Array[String]): Unit = {
    println(sumTo(1000000))
  }
}

tailrec Memerlukan final atau Lokal

Agar @tailrec dapat diterapkan, metode tidak boleh dapat ditimpa: metode tersebut harus private, final, atau metode lokal/bersarang. Metode terbuka dapat ditimpa sehingga merusak optimasi; karena itu kompiler menolaknya.

Catatan tentang Rekursi Mutual

@tailrec hanya mengoptimalkan fungsi yang memanggil dirinya sendiri. Dua fungsi yang saling memanggil (rekursi mutual) tidak dapat dioptimalkan sebagai rekursi-ekor secara langsung oleh JVM; untuk itu Anda memerlukan trampolin, yang akan dibahas nanti.

Pemeriksaan Singkat

Uji pemahaman Anda tentang @tailrec.

Ringkasan

Anda telah mempelajari anotasi @tailrec:

Pemanggilan dalam posisi ekor dapat dioptimalkan menjadi perulangan.
@tailrec memberikan jaminan keamanan tumpukan saat kompilasi.
Metode tersebut harus final, private, atau lokal.
Anotasi ini hanya mencakup rekursi terhadap diri sendiri, bukan rekursi mutual.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Anotasi tailrec” gratis?

Ya — teks lengkap “Anotasi tailrec” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Scala for Backend Engineering & Functional Programming, upgrade ke CoddyKit PRO. Kursus Scala for Backend Engineering & Functional Programming mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Anotasi tailrec”?

Optimasi terjamin. Kamu berlatih Scala for Backend Engineering & Functional Programming dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Scala for Backend Engineering & Functional Programming?

Tidak diperlukan pengalaman sebelumnya. Scala for Backend Engineering & Functional Programming di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.

Berapa lama pelajaran “Anotasi tailrec” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Scala for Backend Engineering & Functional Programming ini?

Ya. Setiap pelajaran Scala for Backend Engineering & Functional Programming menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Scala for Backend Engineering & Functional Programming