รายละเอียดเกี่ยวกับ Recursion

Recursion (การเรียกซ้ำ) คือเทคนิคการเขียนโปรแกรมที่ ฟังก์ชันเรียกตัวเอง เพื่อแก้ปัญหาซับซ้อนด้วยการแบ่งเป็นปัญหาย่อยเล็กๆ ที่มีโครงสร้างเหมือนกัน โดยทุกฟังก์ชัน Recursive ต้องมี 2 ส่วนได้แก่:

ส่วนที่ 1 Base Case (เงื่อนไขสิ้นสุด)

  • เป็นจุดหยุดการเรียกซ้ำ เพื่อป้องกันไม่ให้ฟังก์ชันทำงานไม่สิ้นสุด (Infinite Loop)

  • ตัวอย่าง: ในฟังก์ชันคำนวณแฟคทอเรียล Base Case คือเมื่อ n = 0 หรือ n = 1

ส่วนที่ 2 Recursive Case (เงื่อนไขเรียกซ้ำ)

  • ส่วนที่ฟังก์ชันเรียกตัวเองด้วยข้อมูลที่เล็กลงหรือง่ายขึ้น

  • ตัวอย่าง:

n! = n * (n-1)!

ทำไมต้องใช้ Recursion?

1) ลดความซับซ้อนของโค้ด:

  • โค้ดมักสั้นและอ่านง่ายกว่าการใช้ลูปสำหรับปัญหาบางประเภท

  • เช่น การค้นหาในโครงสร้างต้นไม้ (Tree) ที่มีกิ่งก้านซับซ้อน

2) สอดคล้องกับคณิตศาสตร์:

  • ปัญหาหลายอย่างในคณิตศาสตร์นิยามแบบ Recursive อยู่แล้ว เช่น แฟคทอเรียล ฟีโบนัชชี

3) เหมาะกับโครงสร้างข้อมูลแบบซ้อนกัน:

  • เช่น JSON, XML, ไฟล์ระบบที่มีโฟลเดอร์ซ้อนโฟลเดอร์

Recursion vs. Iteration (การวนลูป)

เมื่อพูดถึงการเขียนโปรแกรมเพื่อแก้ปัญหาซ้ำๆ นักพัฒนามักมีสองทางเลือกหลักคือ Recursion (การเรียกซ้ำ) และ Iteration (การวนลูป) ทั้งคู่มีจุดแข็งและจุดอ่อนแตกต่างกันไป เรามาเจาะลึกกันว่าควรใช้เมื่อไร และทำไม!

1. ประสิทธิภาพ

1) Recursion

  • ใช้หน่วยความจำมากกว่า เพราะทุกครั้งที่ฟังก์ชันเรียกตัวเอง ระบบจะจัดสรรพื้นที่ใน Call Stack เพื่อเก็บสถานะการทำงาน หากเรียกซ้ำลึกเกินไป (เช่น 10,000 ครั้ง) อาจเกิด Stack Overflow

  • ตัวอย่างปัญหา: การคำนวณ Fibonacci แบบธรรมดา (ไม่ใช้ Memoization) จะคำนวณซ้ำหลายครั้ง ส่งผลให้ประสิทธิภาพต่ำ

2) Iteration

  • ใช้หน่วยความจำน้อยกว่า เพราะใช้ลูป (เช่น for, while) ที่ทำงานใน Stack เดิม
  • ตัวอย่าง: การคำนวณ Fibonacci ด้วยลูปทำงานเร็วและประหยัดทรัพยากรกว่า

ตัวอย่างโค้ดเปรียบเทียบ

Recursion (Fibonacci)

def fibonacci(n):  
    if n <= 1:  
        return n  
    return fibonacci(n-1) + fibonacci(n-2)  # สั่งเรียกตัวเอง 2 ครั้ง

Iteration (Fibonacci)

def fibonacci_loop(n):  
    a, b = 0, 1  
    for _ in range(n):  
        a, b = b, a + b  
    return a

2.. การอ่านโค้ด

1) Recursion

  • เหมาะสำหรับปัญหาที่แตกเป็นส่วนย่อย เช่น โครงสร้างต้นไม้ (Tree) ทำให้โค้ดสั้นและตรงไปตรงมา
  • ตัวอย่าง: การค้นหาไฟล์ในไดเรกทอรีย่อย 
def search_file(path, target):  
    if os.path.isfile(path) and path.endswith(target):  
        return path  
    if os.path.isdir(path):  
        for item in os.listdir(path):  
            result = search_file(os.path.join(path, item), target)  
            if result:  
                return result

2) Iteration

  • อาจซับซ้อน หากต้องจัดการหลายเงื่อนไขพร้อมกัน เช่น การเรียงข้อมูลแบบ Bubble Sort
  • ตัวอย่าง: การวนลูปเพื่อค้นหาข้อมูลในลิสต์ 
def find_value(arr, target):  
    for item in arr:  
        if item == target:  
            return True  
    return False

3.. การดีบัก

1) Recursion

  • ยากกว่า เพราะต้องติดตาม Call Stack ที่ซ้อนกันหลายชั้น โดยเฉพาะเมื่อเกิดข้อผิดพลาดในขั้นตอนลึกๆ
  • เทคนิคช่วยเหลือ: เพิ่ม print() เพื่อแสดงค่าการเรียกซ้ำแต่ละครั้ง

2) Iteration

  • ง่ายกว่า เพราะสามารถใช้ breakpoint() หรือ print() ในแต่ละรอบลูปเพื่อตรวจสอบค่า _________________________________________________________________________

ปัญหาไหนเหมาะกับ Recursion?

ตัวอย่าง 1: ท่องต้นไม้ (Tree Traversal)
การท่องต้นไม้แบบ Inorder/Preorder/Postorder ใช้ Recursion ได้อย่างคล่องตัว เพราะโครงสร้างต้นไม้มีลักษณะซ้ำกันในแต่ละโหนด

def inorder_traversal(node):  
    if node:  
        inorder_traversal(node.left)  
        print(node.value)  
        inorder_traversal(node.right)

ตัวอย่าง 2: Tower of Hanoi
ปัญหาคลาสสิกที่นิยมแก้ด้วย Recursion เพราะแบ่งเป็นขั้นตอนย่อยที่เหมือนกัน

def tower_of_hanoi(n, source, auxiliary, target):  
    if n == 1:  
        print(f"ย้ายแผ่น {n} จาก {source} ไป {target}")  
        return  
    tower_of_hanoi(n-1, source, target, auxiliary)  
    print(f"ย้ายแผ่น {n} จาก {source} ไป {target}")  
    tower_of_hanoi(n-1, auxiliary, source, target)

ผลลัพธ์:

ย้ายแผ่นที่ 1 จาก A ไป C  
ย้ายแผ่นที่ 2 จาก A ไป B  
ย้ายแผ่นที่ 1 จาก C ไป B  
ย้ายแผ่นที่ 3 จาก A ไป C  
ย้ายแผ่นที่ 1 จาก B ไป A  
ย้ายแผ่นที่ 2 จาก B ไป C  
ย้ายแผ่นที่ 1 จาก A ไป C

ตัวอย่าง 3: การค้นหาไฟล์ในไดเรกทอรีย่อย

import os  

def find_pdf_files(dir_path):  
    for item in os.listdir(dir_path):  
        full_path = os.path.join(dir_path, item)  
        if os.path.isfile(full_path) and item.endswith(".pdf"):  
            print(f"พบไฟล์ PDF: {full_path}")  
        elif os.path.isdir(full_path):  
            find_pdf_files(full_path)  # เรียกซ้ำเพื่อค้นหาในโฟลเดอร์ย่อย

สรุปเนื้อหา

ข้อดีของ Recursion

  • โค้ดกระชับและสวยงาม สำหรับปัญหาที่มีโครงสร้างซ้ำ
  • สะท้อนแนวคิดคณิตศาสตร์ เช่น การนิยามลำดับ Fibonacci
  • เหมาะกับโครงสร้างข้อมูลแบบ Tree/Graph

ข้อควรระวัง

  • Stack Overflow: การเรียกซ้ำลึกเกินไปอาจทำให้หน่วยความจำเต็ม
  • ประสิทธิภาพต่ำ: บางปัญหามีการคำนวณซ้ำหลายครั้ง

เทคนิคปรับปรุงประสิทธิภาพ
1) Memoization:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
  • ลดการคำนวณซ้ำด้วยการเก็บผลลัพธ์ที่เคยคำนวณแล้ว

2) เปลี่ยนเป็นลูป:

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

การประยุกต์ใช้ในงานอื่นๆ

  • AI/Game Development: การค้นหาเส้นทาง (Pathfinding) ในเกม
  • Data Science: การประมวลผลข้อมูลแบบ Hierarchical Clustering
  • Compiler Design: การแยกวิเคราะห์ไวยากรณ์ (Parsing)

ทิ้งท้าย: Recursion เป็นเครื่องมือทรงพลังที่ต้องใช้อย่างมีสติ! เริ่มจากปัญหาเล็กๆ แล้วค่อยขยับไปปัญหาซับซ้อน จะช่วยให้คุณเห็นภาพการแตกปัญหาอย่างเป็นระบบมากขึ้น 💡

Referrence:

GeeksforGeeks: Recursion vs Iteration
https://www.geeksforgeeks.org/difference-between-recursion-and-iteration/

Stack Overflow: When to Use Recursion vs. Iteration
https://stackoverflow.com/questions/2093618/can-all-iterative-algorithms-be-expressed-recursively

Real Python: Thinking Recursively
https://realpython.com/python-thinking-recursively/