Trampolining
Rekursi yang aman bagi stack.
Trampolining adalah pelajaran Scala for Backend Engineering & Functional Programming gratis di CoddyKit. Ini adalah pelajaran 4 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.
Batasan @tailrec
@tailrec hanya mengoptimalkan fungsi yang secara langsung memanggil dirinya sendiri. Anotasi ini tidak dapat membantu rekursi mutual (dua fungsi yang saling memanggil), yang tetap memperbesar tumpukan. Trampolin menyelesaikan masalah ini.
Masalah Rekursi Mutual
Perhatikan isEven dan isOdd yang didefinisikan berdasarkan satu sama lain. Untuk bilangan besar, pemanggilan ini menyebabkan luapan tumpukan, dan keduanya tidak dapat diberi anotasi @tailrec.
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}Apa Itu Trampolin?
Trampolin mengubah pemanggilan rekursif menjadi data. Alih-alih memanggil dirinya sendiri, fungsi mengembalikan deskripsi langkah berikutnya. Perulangan pengendali menjalankan langkah-langkah ini berulang kali sehingga tumpukan tetap datar.
TailRec di Pustaka Standar
Scala menyediakan scala.util.control.TailCalls dengan tipe TailRec. Gunakan done(x) untuk hasil akhir dan tailcall(...) untuk menunda pemanggilan berikutnya.
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}done dan tailcall
Dua penyusun dasarnya:
done(value)membungkus jawaban akhir.tailcall(expr)menunda pemanggilan yang mengembalikanTailRec.
Memanggil .result menjalankan perulangan trampolin dan menghasilkan nilainya.
Keamanan Tumpukan
Karena setiap tailcall mengembalikan kendali ke perulangan pengendali alih-alih menumpuk pemanggilan Java, tumpukan JVM tidak pernah bertambah mengikuti kedalaman rekursi. Contoh di atas menangani 100.000 langkah tanpa luapan.
Menerapkan Trampolin pada Rekursi Diri
Trampolin juga berfungsi untuk rekursi diri biasa yang dalam ketika Anda tidak dapat menggunakan akumulator dengan mudah. Di sini, countdown yang dalam tetap aman terhadap tumpukan.
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}Menggabungkan Hasil dengan flatMap
TailRec mendukung map dan flatMap, sehingga Anda dapat melakukan pekerjaan setelah pemanggilan yang ditunda sambil tetap aman terhadap tumpukan.
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}Cara Kerja Perulangan Pengendali
Secara konseptual, .result menjalankan perulangan: ambil langkah saat ini; jika langkah tersebut berupa done, kembalikan nilainya; jika berupa pemanggilan yang ditunda, evaluasi satu lapisan lalu lanjutkan. Semuanya menggunakan ruang tumpukan konstan.
Trampolin dalam Pustaka Efek
Pustaka seperti Cats Effect dan ZIO secara internal menerapkan trampolin pada rantai flatMap, sehingga Anda dapat membangun program efek bertingkat dalam tanpa luapan tumpukan. Trampolin merupakan dasar efek fungsional yang aman terhadap tumpukan.
Kapan Menggunakan Trampolin
Gunakan trampolin ketika:
- Anda memiliki rekursi mutual yang tidak dapat dijadikan satu fungsi rekursif ekor.
- Rekursinya terlalu dalam bagi tumpukan dan akumulator tidak sesuai digunakan.
Untuk rekursi diri yang sederhana, dahulukan @tailrec dengan akumulator.
Pemeriksaan Singkat
Uji pemahaman Anda tentang penggunaan trampolin.
Rangkuman
Anda telah mempelajari penggunaan trampolin:
- Teknik ini membuat rekursi mutual dan rekursi yang sangat dalam aman terhadap tumpukan.
- Gunakan
TailCalls:done(x)dantailcall(...), lalu.result. TailRecmendukungmap/flatMap.- Teknik ini menjadi dasar pustaka efek yang aman terhadap tumpukan.
Belajar Scala dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 39
- Pelajaran
- 143
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Trampolining” gratis?
Ya — teks lengkap “Trampolining” 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 “Trampolining”?
Rekursi yang aman bagi stack. 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 4 dari 4.
Berapa lama pelajaran “Trampolining” 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.