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 บทเรียน

ความหมายของการเรียกซ้ำ

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

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

ฟังก์ชันแบบเรียกซ้ำทุกฟังก์ชันต้องมีสองสิ่ง ได้แก่ วิธีหยุด และวิธีทำให้ปัญหาเล็กลง

กรณีฐานต้องมาก่อน

กรณีฐานคืออินพุตที่ง่ายที่สุดซึ่งฟังก์ชันสามารถตอบได้โดยตรง โดยไม่ต้องเรียกซ้ำต่อ

หากไม่มีกรณีฐาน ฟังก์ชันจะเรียกตัวเองไปเรื่อย ๆ และหยุดทำงานเนื่องจากสแตกเต็ม

ควรออกแบบกรณีฐานก่อนขั้นตอนการเรียกซ้ำเสมอ

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

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

นี่คือตัวอย่างโปรแกรมสมบูรณ์ที่หาผลรวมตัวเลขตั้งแต่ 1 ถึง n

กรณีฐานคืนค่า 0 ส่วนกรณีเรียกซ้ำจะนำ n มาบวกกับผลรวมของตัวเลขทั้งหมดที่น้อยกว่า n

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

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

การไล่ดูการเรียกฟังก์ชัน

หากต้องการทำความเข้าใจการเรียกซ้ำ ให้ขยายการเรียกฟังก์ชันด้วยตนเอง

sum(3) กลายเป็น 3 + sum(2) ซึ่งกลายเป็น 3 + 2 + sum(1) แล้วจึงเป็น 3 + 2 + 1 + sum(0)

เมื่อ sum(0) คืนค่า 0 เท่านั้น ลำดับการเรียกจึงจะยุบกลับมาเป็นค่าเดียว นั่นคือ 6

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

การเรียกซ้ำกับลิสต์

ลิสต์มีลักษณะเป็นการเรียกซ้ำโดยธรรมชาติ กล่าวคือ ลิสต์อาจว่างเปล่า (ลิสต์ว่าง) หรือประกอบด้วยส่วนหัวตามด้วยส่วนท้ายที่เล็กลง

โครงสร้างนี้สอดคล้องกับฟังก์ชันแบบเรียกซ้ำโดยตรง ลิสต์ว่างคือกรณีฐาน ส่วนส่วนหัวบวกกับการเรียกซ้ำกับส่วนท้ายคือขั้นตอนการเรียกซ้ำ

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

การจับคู่รูปแบบกับส่วนท้าย

รูปแบบ :: จะแยกลิสต์ที่ไม่ว่างออกเป็นส่วนหัวและส่วนท้าย

การเรียกซ้ำแต่ละครั้งทำงานกับลิสต์ที่สั้นลงอย่างชัดเจน จึงรับประกันว่าจะเคลื่อนไปสู่ลิสต์ว่าง

นี่คือวิธีมาตรฐานสำหรับวนผ่านลิสต์ด้วยการเรียกซ้ำใน 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

การเรียกซ้ำสองครั้ง

ปัญหาบางประเภทแตกแขนงออกเป็นการเรียกซ้ำมากกว่าหนึ่งครั้ง

ตัวอย่างคลาสสิกคือฟีโบนัชชี ซึ่งแต่ละค่าขึ้นอยู่กับสองค่าก่อนหน้า

เวอร์ชันพื้นฐานนี้เข้าใจง่ายแต่ทำงานช้า เพราะคำนวณค่าเดิมซ้ำหลายครั้ง

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

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

ต้นทุนของสแตก

การเรียกซ้ำแต่ละครั้งจะเพิ่มเฟรมเข้าไปในสแตกการเรียก ซึ่งต้องรอให้การเรียกด้านในส่งค่ากลับมา

หากเรียกซ้ำลึกมาก อาจใช้พื้นที่สแตกจนหมดและทำให้เกิด StackOverflowError

การนับความลึก ไม่ใช่ดูเพียงขนาดของข้อมูล จะช่วยให้คุณคาดการณ์ความเสี่ยงนี้ได้

// 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

ลดขนาดเข้าใกล้กรณีฐาน

คุณสมบัติสำคัญที่ต้องคงไว้ของการเรียกซ้ำคือ การเรียกทุกครั้งต้องขยับเข้าใกล้กรณีฐานมากขึ้น

หากอาร์กิวเมนต์ไม่เล็กลง หรือไม่เคยไปถึงเงื่อนไขหยุด การเรียกซ้ำก็จะไม่สิ้นสุด

ตรวจสอบเรื่องนี้ก่อนเรียกใช้โปรแกรมใด ๆ

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

การเรียกซ้ำเทียบกับลูป

โค้ดเชิงคำสั่งใช้ลูป while กับตัวนับที่เปลี่ยนค่าได้ ส่วนโค้ดเชิงฟังก์ชันใช้การเรียกซ้ำกับค่าที่แก้ไขไม่ได้

ทั้งสองแบบสามารถแสดงการคำนวณเดียวกันได้ แต่การเรียกซ้ำอธิบายโครงสร้างของข้อมูลได้โดยตรงกว่า

ใน Scala คุณมักเลือกใช้การเรียกซ้ำหรือฟังก์ชันลำดับสูงแทนลูปแบบพื้นฐาน

// 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)

การออกแบบวิธีแก้ปัญหาแบบเรียกซ้ำ

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

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

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

ตรวจสอบความเข้าใจ

ทดสอบความเข้าใจของคุณเกี่ยวกับโครงสร้างแบบเรียกซ้ำ

สรุปทบทวน

การเรียกซ้ำแก้ปัญหาโดยลดปัญหานั้นให้เป็นกรณีที่เล็กลงของตัวมันเอง

ฟังก์ชันแบบเรียกซ้ำทุกฟังก์ชันต้องมีกรณีฐานเพื่อหยุด และมีขั้นตอนการเรียกซ้ำที่ลดขนาดอินพุตให้เข้าใกล้กรณีฐาน

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

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

บทเรียน “คิดแบบเรียกซ้ำ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “คิดแบบเรียกซ้ำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ 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 ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

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

← กลับไปที่ Scala for Backend Engineering & Functional Programming