Skip to main content

recursion-and-divide-and-conquer-algorithms

การทำความเข้าใจเกี่ยวกับ Recursion และ Divide-and-Conquer Algorithms เป็นเรื่องสำคัญในการเขียนโปรแกรมและแก้ปัญหาที่ซับซ้อน โดยทั้งสองแนวคิดนี้เกี่ยวข้องกับการแบ่งปัญหาย่อยและการเรียกใช้ฟังก์ชันซ้ำๆ เพื่อหาคำตอบ

1. Recursion (การเรียกซ้ำ)​

Recursion คือกระบวนการที่ฟังก์ชันเรียกตัวเองในระหว่างการทำงาน ฟังก์ชันจะทำการประมวลผลและคำนวณผลลัพธ์จนกว่าจะถึงเงื่อนไขฐาน (base case) ซึ่งจะหยุดการเรียกซ้ำ

ลักษณะสำคัญของ Recursion:​

  • Base Case: เงื่อนไขที่ใช้หยุดการเรียกซ้ำ
  • Recursive Case: การเรียกฟังก์ชันซ้ำโดยลดขนาดของปัญหาลง

ตัวอย่างของ Recursion ในการคำนวณเลข Fibonacci​

def fibonacci(n):
    # Base case: ถ้า n เป็น 0 หรือ 1
    if n <= 1:
        return n
    # Recursive case: เรียกฟังก์ชันตัวเอง
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# การทดสอบฟังก์ชัน Fibonacci
print(fibonacci(5))  # Output: 5

ผลลัพธ์ของการคำนวณ Fibonacci(5):

  • เรียกฟังก์ชันซ้ำจนได้คำตอบ: fibonacci(5) จะคำนวณเป็น fibonacci(4) + fibonacci(3) จนถึง fibonacci(0) และ fibonacci(1) ซึ่งเป็น base case

ข้อดีของ Recursion:​

  • เขียนโค้ดที่สั้นและเข้าใจง่ายสำหรับปัญหาที่มีลักษณะซ้ำซ้อน
  • ใช้งานได้ดีในปัญหาที่มีโครงสร้างข้อมูลเป็นต้นไม้ (Tree) หรือกราฟ (Graph)

ข้อเสียของ Recursion:​

  • ถ้าไม่มีการจัดการที่ดีจะทำให้เกิด Stack Overflow (กรณีฟังก์ชันเรียกซ้ำเกินไป)
  • ประสิทธิภาพต่ำในบางกรณี (เช่น Fibonacci ข้างต้น ที่คำนวณซ้ำหลายครั้ง)

2. Divide-and-Conquer Algorithms (อัลกอริธึมแบบแบ่งและพิชิต)​

Divide-and-Conquer (แบ่งและพิชิต) คือแนวคิดในการแก้ปัญหาที่มีลักษณะสามารถแบ่งออกเป็นปัญหาย่อยๆ แล้วรวมผลลัพธ์จากปัญหาย่อยเหล่านั้นมาเป็นคำตอบที่สมบูรณ์

แนวทางของ Divide-and-Conquer:​

  1. Divide: แบ่งปัญหาออกเป็นปัญหาย่อยๆ ที่ขนาดเล็กกว่า
  2. Conquer: แก้ไขปัญหาย่อยๆ ด้วยวิธีการที่คล้ายกับการแก้ปัญหาหลัก
  3. Combine: รวมคำตอบจากปัญหาย่อยเพื่อหาคำตอบของปัญหาหลัก

ตัวอย่างของ Divide-and-Conquer: Merge Sort​

Merge Sort เป็นอัลกอริธึมที่ใช้แนวคิด Divide-and-Conquer โดยการแบ่งลิสต์ออกเป็นสองส่วน แล้วเรียงลำดับแต่ละส่วน จากนั้นจึงรวมผลลัพธ์เข้าด้วยกัน

ขั้นตอนการทำงานของ Merge Sort:​

  1. Divide: แบ่งลิสต์ออกเป็นสองส่วน
  2. Conquer: เรียงลำดับแต่ละส่วน
  3. Combine: รวมลิสต์ที่เรียงแล้วเข้าด้วยกัน

ตัวอย่างโค้ด Merge Sort:​

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Combine
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# การทดสอบ Merge Sort
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # Output: [3, 9, 10, 27, 38, 43, 82]

การทำงาน:

  • Divide: ลิสต์ [38, 27, 43, 3, 9, 82, 10] ถูกแบ่งเป็น [38, 27, 43] และ [3, 9, 82, 10]
  • Conquer: แต่ละส่วนถูกเรียงโดยใช้ Merge Sort
  • Combine: ผลลัพธ์ที่เรียงแล้วถูกรวมเข้าด้วยกัน

ข้อดีของ Divide-and-Conquer:​

  • มีประสิทธิภาพดีมากในบางกรณี เช่น Merge Sort, Quick Sort
  • ช่วยให้แก้ปัญหาขนาดใหญ่ได้โดยการลดขนาดของปัญหาลงในแต่ละขั้นตอน
  • สามารถใช้ร่วมกับการ Parallel Processing (การประมวลผลขนาน) ได้

ข้อเสียของ Divide-and-Conquer:​

  • อาจจะมีการใช้หน่วยความจำมากขึ้น เช่น Merge Sort ที่ต้องใช้พื้นที่หน่วยความจำในการจัดเก็บข้อมูลชั่วคราว
  • การรวมผลลัพธ์จากส่วนย่อยอาจเป็นปัญหาในบางกรณี

3. เปรียบเทียบ Recursion และ Divide-and-Conquer​

  • Recursion: การเรียกฟังก์ชันตัวเองซ้ำๆ เพื่อแก้ปัญหาในขั้นตอนย่อยๆ จนถึง Base Case
  • Divide-and-Conquer: การแบ่งปัญหาขนาดใหญ่เป็นปัญหาย่อยๆ และนำมารวมผลลัพธ์เพื่อหาคำตอบ

การใช้ Recursion ใน Divide-and-Conquer​

จริงๆ แล้ว Divide-and-Conquer มักจะใช้ Recursion ในการแบ่งปัญหาย่อย ตัวอย่างเช่นใน Merge Sort และ Quick Sort

4. ตัวอย่างอื่นๆ ที่ใช้ Recursion และ Divide-and-Conquer​

  • Binary Search: การค้นหาข้อมูลในลิสต์ที่เรียงลำดับแล้ว โดยการแบ่งครึ่งลิสต์เพื่อค้นหาครั้งละหนึ่งครึ่ง
  • Quick Sort: การเรียงลำดับโดยการเลือก Pivot และแบ่งข้อมูลที่น้อยกว่าหรือมากกว่ามาเรียง
  • Tree Traversal: การค้นหาหรือประมวลผลข้อมูลในต้นไม้ (Tree) โดยใช้การเรียกฟังก์ชันซ้ำๆ

สรุป​

  • Recursion: คือการที่ฟังก์ชันเรียกตัวเองเพื่อแก้ปัญหาย่อยจนถึงเงื่อนไขฐาน
  • Divide-and-Conquer: คือการแบ่งปัญหาขนาดใหญ่เป็นปัญหาย่อยๆ แล้วรวมคำตอบจากปัญหาย่อยเหล่านั้น
  • ทั้งสองแนวคิดนี้มักใช้ร่วมกันในการแก้ปัญหาซับซ้อน เช่น Merge Sort, Quick Sort, และ Binary Search