0Pricing
Scala for Backend Engineering & Functional Programming · บทเรียน

พื้นฐานการเรียกซ้ำ

ฟังก์ชันเรียกซ้ำ

พื้นฐานการเรียกซ้ำ เป็นบทเรียน Scala for Backend Engineering & Functional Programming ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Scala for Backend Engineering & Functional Programming และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Scala for Backend Engineering & Functional Programming มีบทเรียนทั้งหมด 4 บทเรียน

การเรียกซ้ำคืออะไร

การเรียกซ้ำ คือการที่ฟังก์ชันเรียกตัวเองเพื่อแก้ปัญหาขนาดเล็กลงแต่เป็นปัญหาแบบเดียวกัน วิธีนี้เหมาะกับการเขียนโปรแกรมเชิงฟังก์ชันตามธรรมชาติ และใช้คำจำกัดความที่อ้างอิงตัวเองแทนลูปจำนวนมาก

สองส่วนสำคัญ

ฟังก์ชันแบบเรียกซ้ำที่ถูกต้องทุกฟังก์ชันต้องมี:

  • กรณีฐาน ที่หยุดการเรียกซ้ำ
  • กรณีเรียกซ้ำ ที่ทำให้เข้าใกล้กรณีฐาน

หากไม่สามารถไปถึงกรณีฐานได้ การเรียกซ้ำจะทำงานต่อไปไม่สิ้นสุด

แฟกทอเรียล

ตัวอย่างคลาสสิกคือ n! = n * (n-1)! โดยมี 0! = 1 เป็นกรณีฐาน

object Main {
  def factorial(n: Int): Int =
    if (n <= 1) 1
    else n * factorial(n - 1)

  def main(args: Array[String]): Unit = {
    println(factorial(5))
  }
}

ติดตามการเรียกฟังก์ชัน

การเรียกซ้ำแต่ละครั้งจะหยุดรอผลลัพธ์จากการเรียกด้านใน factorial(3) จะขยายเป็น 3 * (2 * (1)) การคูณจะเกิดขึ้นเมื่อการเรียกแต่ละชั้นส่งค่ากลับ

object Main {
  def factorial(n: Int): Int = {
    println(s"entering factorial($n)")
    if (n <= 1) 1 else n * factorial(n - 1)
  }

  def main(args: Array[String]): Unit = {
    println("result = " + factorial(3))
  }
}

ผลรวมของลิสต์

การเรียกซ้ำบนลิสต์: ผลรวมคือสมาชิกตัวหน้า บวกกับผลรวมของส่วนที่เหลือ โดยลิสต์ว่างมีผลรวมเป็นศูนย์

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

  def main(args: Array[String]): Unit = {
    println(sum(List(1, 2, 3, 4)))
  }
}

ความยาวของลิสต์

ใช้รูปแบบเดียวกันคำนวณความยาวได้: ลิสต์ว่างมีค่าเป็น 0 มิฉะนั้นให้บวก 1 กับความยาวของส่วนที่เหลือ

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

  def main(args: Array[String]): Unit = {
    println(length(List("a", "b", "c")))
  }
}

สแตกการเรียกฟังก์ชัน

การเรียกซ้ำแต่ละครั้งที่ยังรอผลลัพธ์จะใช้ เฟรมของสแตก การเรียกซ้ำที่ลึกจะสะสมเฟรมจำนวนมาก สำหรับข้อมูลเข้าขนาดใหญ่มาก อาจใช้สแตกจนหมดและทำให้เกิด StackOverflowError

ฟีโบนัชชี

ปัญหาบางอย่างแตกแขนงเป็นการเรียกซ้ำหลายครั้ง ฟังก์ชันฟีโบนัชชีเรียกตัวเองสองครั้ง ซึ่งดูสวยงามแต่มีต้นทุนเพิ่มขึ้นแบบเอ็กซ์โพเนนเชียล

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

  def main(args: Array[String]): Unit = {
    println(fib(10))
  }
}

การกลับลำดับลิสต์

การเรียกซ้ำสามารถสร้างโครงสร้างใหม่ได้: reverse จะนำสมาชิกตัวหน้าไปต่อท้ายหลังจากกลับลำดับส่วนที่เหลือแล้ว

object Main {
  def reverse[A](xs: List[A]): List[A] = xs match {
    case Nil    => Nil
    case h :: t => reverse(t) :+ h
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3)))
  }
}

การเรียกซ้ำเทียบกับการวนซ้ำ

ลูปเปลี่ยนค่าตัวนับ ส่วนการเรียกซ้ำอธิบายปัญหาในเชิงประกาศ ทั้งสองวิธีใช้ได้ การเรียกซ้ำเหมาะอย่างยิ่งกับข้อมูลรูปต้นไม้และการแบ่งแล้วพิชิต แต่การเรียกซ้ำแบบไม่ปรับปรุงอาจทำให้สแตกเต็มเมื่อข้อมูลเข้าเชิงเส้นมีขนาดใหญ่

ตัวหารร่วมมาก

ขั้นตอนวิธีของยูคลิดเหมาะกับการเขียนแบบเรียกซ้ำตามธรรมชาติและลู่เข้าสู่คำตอบได้อย่างรวดเร็ว

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

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

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทดสอบพื้นฐานเรื่องการเรียกซ้ำของคุณ

สรุปทบทวน

คุณได้เรียนรู้ พื้นฐานการเรียกซ้ำ:

  • ฟังก์ชันแบบเรียกซ้ำทุกฟังก์ชันต้องมี กรณีฐาน และ กรณีเรียกซ้ำ
  • การเรียกแต่ละครั้งที่ยังรอผลลัพธ์จะใช้เฟรมของสแตก การเรียกซ้ำที่ลึกอาจทำให้สแตกเต็ม
  • การเรียกซ้ำเหมาะกับการเขียนขั้นตอนวิธีบนลิสต์และต้นไม้

ถัดไป คุณจะทำให้การเรียกซ้ำปลอดภัยต่อสแตกด้วยคำอธิบายประกอบ @tailrec

คำถามที่พบบ่อย

บทเรียน “พื้นฐานการเรียกซ้ำ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “พื้นฐานการเรียกซ้ำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Scala for Backend Engineering & Functional Programming ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Scala for Backend Engineering & Functional Programming มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “พื้นฐานการเรียกซ้ำ”

ฟังก์ชันเรียกซ้ำ คุณปฏิบัติ Scala for Backend Engineering & Functional Programming ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Scala for Backend Engineering & Functional Programming หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Scala for Backend Engineering & Functional Programming บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน

บทเรียน “พื้นฐานการเรียกซ้ำ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Scala for Backend Engineering & Functional Programming นี้ได้ไหม

ได้ บทเรียน Scala for Backend Engineering & Functional Programming ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. พื้นฐานการเรียกซ้ำ
  2. แอนโนเทชัน tailrec
  3. รูปแบบตัวสะสม
  4. แทรมโพลีน
← กลับไปที่ Scala for Backend Engineering & Functional Programming