Scala for Backend Engineering & Functional Programming · Pelajaran

Berpikir Secara Rekursif

Kasus dasar dan langkah rekursif.

Berpikir Secara Rekursif adalah pelajaran Scala for Backend Engineering & Functional Programming gratis di CoddyKit. Ini adalah pelajaran 1 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.

Makna Rekursi

Rekursi adalah saat sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan versi yang lebih kecil dari masalah yang sama.

Dalam Scala, rekursi cocok secara alami untuk pemrograman fungsional karena memungkinkan Anda menyatakan perulangan tanpa variabel yang dapat diubah.

Setiap fungsi rekursif memerlukan dua hal: cara untuk berhenti dan cara untuk memperkecil masalah.

Kasus Dasar Terlebih Dahulu

Kasus dasar adalah input paling sederhana yang dapat dijawab fungsi secara langsung, tanpa rekursi lanjutan.

Tanpa kasus dasar, fungsi akan terus memanggil dirinya sendiri dan gagal karena luapan tumpukan.

Selalu rancang kasus dasar sebelum langkah rekursif.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

Fungsi Rekursif Pertama

Berikut program lengkap yang menjumlahkan angka dari 1 hingga n.

Kasus dasar mengembalikan 0; kasus rekursif menambahkan n ke jumlah semua angka di bawahnya.

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

@main def run(): Unit =
  println(sum(5))   // 15

Menelusuri Pemanggilan

Untuk memahami rekursi, uraikan pemanggilannya secara manual.

sum(3) menjadi 3 + sum(2), lalu menjadi 3 + 2 + sum(1), kemudian 3 + 2 + 1 + sum(0).

Rangkaian ini baru menyatu kembali menjadi satu nilai, yaitu 6, setelah sum(0) mengembalikan 0.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Rekursi pada List

List secara alami bersifat rekursif: sebuah list bisa kosong (Nil) atau terdiri dari kepala yang diikuti ekor yang lebih kecil.

Bentuk ini langsung sesuai dengan fungsi rekursif. List kosong adalah kasus dasar; kepala ditambah rekursi pada ekor adalah langkah rekursif.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

Pencocokan Pola pada Ekor

Pola :: memisahkan list yang tidak kosong menjadi kepala dan ekornya.

Setiap pemanggilan rekursif bekerja pada list yang lebih pendek, sehingga kemajuan menuju Nil selalu terjamin.

Ini adalah cara standar untuk menelusuri list secara rekursif dalam Scala.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

Dua Pemanggilan Rekursif

Beberapa masalah bercabang menjadi lebih dari satu pemanggilan rekursif.

Contoh klasiknya adalah Fibonacci, yang setiap nilainya bergantung pada dua nilai sebelumnya.

Versi naif ini sederhana tetapi lambat karena menghitung ulang nilai yang sama berkali-kali.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

Biaya Tumpukan

Setiap pemanggilan rekursif menambahkan bingkai ke tumpukan pemanggilan, yang harus menunggu pemanggilan di dalamnya selesai.

Untuk rekursi yang sangat dalam, hal ini dapat menghabiskan tumpukan dan memunculkan StackOverflowError.

Menghitung kedalaman, bukan hanya ukuran, membantu Anda memperkirakan risiko ini.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Menyusut Menuju Kasus Dasar

Invarian utama rekursi adalah setiap pemanggilan harus bergerak mendekati kasus dasar.

Jika argumen tidak menjadi lebih kecil atau tidak pernah mencapai kondisi penghentian, rekursi tidak akan berakhir.

Periksa hal ini sebelum menjalankan apa pun.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Rekursi vs Perulangan

Kode imperatif menggunakan perulangan while dengan penghitung yang dapat diubah; kode fungsional menggunakan rekursi dengan nilai yang tidak dapat diubah.

Keduanya dapat menyatakan perhitungan yang sama, tetapi rekursi menggambarkan struktur data secara lebih langsung.

Dalam Scala, Anda akan sering lebih memilih rekursi atau fungsi tingkat tinggi daripada perulangan biasa.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Merancang Solusi Rekursif

Langkah yang andal: tentukan kasus dasar, anggap pemanggilan rekursif sudah bekerja pada input yang lebih kecil, lalu gabungkan kepala dengan hasil tersebut.

Lompatan keyakinan ini adalah inti dari cara berpikir rekursif. Anda memercayai pemanggilan yang lebih kecil dan hanya menangani satu langkah.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Pemeriksaan Singkat

Uji pemahaman Anda tentang struktur rekursif.

Ringkasan

Rekursi menyelesaikan masalah dengan menguranginya menjadi contoh yang lebih kecil dari masalah itu sendiri.

Setiap fungsi rekursif memerlukan kasus dasar untuk berhenti dan langkah rekursif yang memperkecil input menuju kasus dasar tersebut.

List, dengan bentuk Nil serta kepala dan ekor, merupakan tempat yang ideal untuk melatih cara berpikir rekursif. Perhatikan kedalaman tumpukan pada input yang sangat besar.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Berpikir Secara Rekursif” gratis?

Ya — teks lengkap “Berpikir Secara Rekursif” 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 “Berpikir Secara Rekursif”?

Kasus dasar dan langkah rekursif. 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 1 dari 4.

Berapa lama pelajaran “Berpikir Secara Rekursif” 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