ในบทที่แล้วได้อธิบายถึงการใช้ฟังก์ชันไปแล้ว สำหรับบทนี้จะพูดถึงรูปแบบหนึ่งของฟังก์ชันซึ่งมีลักษณะที่ค่อนข้างพิเศษ เรียกว่าฟังก์ชันเวียนเกิด (recursive function)

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

อธิบายด้วยคำพูดแบบนี้ยังไงก็คงจะยังเข้าใจยากอยู่ มาดูตัวอย่างน่าจะช่วยให้เห็นภาพชัดกว่า



แฟ็กทอเรียล

ฟังก์ชันแฟ็กทอเรียลนั้นเป็นหนึ่งในตัวอย่างที่ง่ายที่สุดของการใช้ฟังก์ชันเวียนเกิด

ลองดูตัวอย่างการใช้ สร้างฟังก์ชัน $fac(x) = x! = 1×2×3×...×x$

def fac(x):
    if(x>1):
        return fac(x-1)*x
    else:
        return 1

print(fac(6)) # ได้ 720 

จะเห็นว่าฟังก์ชัน fac ในที่นี้มีการเรียกตัวมันเองคือฟังก์ชัน fac ซ้ำอีกภายในนั้น การเรียกซ้ำนี้จะเกิดขึ้นตราบใดที่ยังมากกว่า 1 แต่ถ้าเป็น 1 จะคืนค่า 1 โดยไม่มีการเรียกซ้ำ

ลองนึกตามทีละขั้น สมมุติเราเรียกใช้ฟังก์ชันโดยใส่อาร์กิวเมนต์เป็น 1 คือ fac(1)

แบบนี้ฟังก์ชันจะเข้า else ทันทีเพราะ x เป็น 1 ดังนั้นจึงคืนค่า 1 กลับมา ซึ่งเป็นไปตามที่ควรจะเป็น

ต่อไปลองคิดกรณี fac(2)

กรณี นี้เมื่อเรียกใช้ x=2 จะเข้าเงื่อนไขแรก ซึ่งจะต้อง return fac(x-1)*x ทำให้มีการเรียกใช้ฟังก์ชันนั้นซ้ำ แต่คราวนี้อาร์กิวเมนต์ต่างไปโดยลดลงไป 1 เป็น x-1 ก็คือเหลือ 1

ซึ่งจะคืนค่า 1 กลับมา จากนั้นก็ถูกนำไปคูณกับ x ก็คือ 2 ดังนั้นผลที่ได้ก็คือได้ 2

คิดต่อไป กรณี fac(3)

เมื่อ เรียกใช้ x=3 จะเข้าเงื่อนไขแรก เรียก return fac(x-1)*x เมื่อแทนค่า x จะได้เป็น return fac(2)*3 ซึ่ง fac(2) ก็รู้ค่าแล้วจากกรณี x=2 ว่าเป็น 2 ดังนั้นเอามาคูณกันก็ได้ผลลัพธ์เป็น 6

กรณี x=4 ก็จะ return fac(3)*4 จึงได้ผลเป็น 24
กรณี x=5 ก็จะ return fac(4)*3 จึงได้ผลเป็น 120
กรณี x=6 ก็จะ return fac(5)*4 จึงได้ผลเป็น 720
...

เป็นอย่างนี้ซ้ำไปเรื่อยๆเป็นจำนวนครั้งตามค่าของ x ที่ใส่ลงไป

เพราะเมื่อเรียกใช้ฟังก์ชัน ภายในฟังก์ชันจะมีการเรียกฟังก์ชันเดิมซ้ำด้วย x ที่ต่ำลงไปทีละขั้น พอเรียกซ้ำก็จะเรียก x ที่ต่ำลงไปเรื่อยๆจนในที่สุดก็เป็น 1 และไม่มีการเรียกซ้ำอีก

สุดท้ายผลที่ได้จึงเป็นการคูณสะสมเพิ่มไปเรื่อยๆ กลายเป็นฟังก์ชันแฟ็กทอเรียลตามที่ต้องการ

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

def fac(x):
    f = 1 # ตั้งต้นที่ 1
    for i in range(2,x+1): # ใช้ for วนซ้ำ ไล่ตั้งแต่ 2
        f = f*i # คูณเพิ่มไปเรื่อยๆ
    return f # คืนผลลัพธ์ที่ได้กลับไป

print(fac(6))

ข้อดีข้อเสียของการใช้ฟังก์ชันแบบเวียนเกิดเมื่อเทียบกับการไม่ใช้

ข้อดี
- หากใช้ได้คล่องแล้วจะมองปัญหาออกได้ง่ายขึ้น เข้าใจง่ายกว่า
- เขียนแล้วดูสั้นกว่า
- ง่ายกว่ามากในกรณีที่มีการทำซ้ำซ้อนกันเป็นวังวนในจำนวนที่ไม่แน่นอน

ข้อเสีย
- เปลืองหน่วยความจำมากกว่า
- ในบางกรณีอาจทำงานช้ากว่า

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

ดังนั้นที่สำคัญคือมองปัญหาให้ออกว่าเวลาไหนควรจะใช้ เลือกใช้ตามความเหมาะสม

เพื่อให้เห็นภาพชัดลองดูตัวอย่างอื่นเปรียบเทียบกันอีก



ฟีโบนัชชี

ลำดับฟีโบนัชชี (Fibonacci) คือลำดับที่มีสมาชิก ๒ ตัวแรกมีค่าเท่ากับ 1 นอกนั้นตัวถัดไปจะมีค่าเท่ากับสองตัวก่อนหน้าบวกกัน
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...



ลองมาเขียนเป็นฟังก์ชันในไพธอนดู

def fib(x):
    if(x>2):
        return fib(x-1)+fib(x-2)
    else:
        return 1

print(fib(8)) 

จะเห็นว่าฟังก์ชันนี้มีการกำหนดเงื่อนไขตามที่ได้กล่าวข้างต้น คือถ้า x เป็นตัวที่ 1 หรือ 2 จะมีค่าเป็น 1 แต่ถ้าเป็นตัวถัดจากนั้นจะมีค่าเท่ากับสองตัวก่อนหน้าบวกกัน

ฟังก์ชันแบบนี้ถ้าไม่ใช้เป็นแบบเวียนเกิด ใช้การวนซ้ำธรรมดาจะเป็นอย่างไร

def fib(x):
    a = 1
    b = 1
    f = 1
    for i in range(3,x+1):
        f = a+b
        a = b
        b = f
    return f

print(fib(8)) 

คราวนี้จะเห็นว่าใช้ฟังก์ชันแบบเวียนเกิดดูแล้วการเขียนดูเรียบง่ายกว่าพอสมควร

แต่อย่างไรก็ตาม ภายใต้ความเรียบง่ายของมัน ก็แฝงไปด้วยความน่ากลัว

ลองพิจารณาดูจะเห็นว่ากรณีใช้ฟังก์ชันเวียนเกิดนั้นเมื่อเรียกใช้ฟังก์ชันครั้ง หนึ่งจะมีการเรียกตัวมันเองถึง ๒ ครั้ง คือ fib(x) จะมีการเรียก fib(x-1) และ fib(x-2) ขึ้นมา

และภายในนั้น fib(x-1) ก็จะทำการเรียก fib(x-2) และ fib(x-3) ส่วน fib(x-2) ก็ไปเรียก fib(x-3) กับ fib(x-4) แล้วก็วนเรียกซ้ำเพิ่มไปเรื่อยๆ จำนวนครั้งที่เรียกมีแต่จะเพิ่มขึ้นเรื่อยๆเป็นทวีคูณ

การเรียกในแต่ละครั้งเป็นการคำนวณใหม่ทุกครั้ง แม้ว่า fib(x-2) จะถูกเรียกซ้ำ 2 ครั้ง fib(x-3) ถูกเรียกซ้ำ 3 ครั้ง แต่มันก็ไม่ได้เก็บค่าเดิมเอาไว้ แต่กลับคำนวณใหม่แยกกัน

ผลก็คือเครื่องทำงานหนักและประสิทธิภาพการทำงานต่ำ

ในขณะที่ถ้าใช้ for วนซ้ำธรรมดา ตัวแปรมีการเก็บค่าเสร็จแล้วก็นำมาใช้แล้วล้างใหม่ทุกรอบ พอเป็นแบบนี้แล้วเครื่องจึงทำงานเบากว่ามาก

สรุป กรณีนี้ฟังก์ชันเวียนเกิดเขียนง่ายแต่ประสิทธิภาพแย่ ฟิโบนัชชีจึงเป็นตัวอย่างของกรณีที่ไม่ควรจะใช้

บางครั้งการเขียนสั้นไม่ได้แปลว่าเป็นโปรแกรมที่ดี ต้องพิจารณาด้วยว่าโปรแกรมมีการทำงานอย่างไรอยู่เบื้องหลังคำสั่งนั้น



ฟังก์ชันสำหรับยุบลิสต์

ลองดูตัวอย่างการใช้ที่ไม่ได้เกี่ยวข้องกับฟังก์ชันทางคณิตศาสตร์กันบ้าง

ตัวอย่างหนึ่งที่จะช่วยให้เห็นว่าใช้ฟังก์ชันเวียนเกิดแล้วง่ายก็คือการยุบลิสต์

สมมุติว่ามีลิสต์หน้าตาซับซ้อนแบบนี้อยู่ [[['a','b'],['c','d']],[['e','f'],['g',['h','i']]],['j','k'],'l']

จะเห็นว่าเป็นลิสต์ซ้อนกันหลายชั้น สูงสุดคือ h กับ i นี้ซ้อนอยู่ในชั้นที่ ๔ คือเป็นลิสต์ในลิสต์ในลิสต์ในลิสต์

เราจะทำให้ทั้งหมดนี้มาอยู่ในลิสต์อันเดียว คือกลายเป็น ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l']

สามารถทำได้ด้วยการสร้างฟังก์ชันเวียนเกิด

def yup(l):
    y = [] # สร้างลิสต์เปล่าขึ้นมาก่อน
    for c in l:
        if(type(c)==list): # ตรวจชนิดของสมาชิกว่าเป็นลิสต์หรือเปล่า
            y += yup(c) # ถ้าเป็นลิสต์ให้เรียกฟังก์ชันซ้ำเพื่อยุบก่อนค่อยเพิ่มเข้าไป
        else:
            y += [c] # ถ้าไม่ใช่ลิสต์ให้เพิ่มเข้าไปในสมาชิก
    return y # คืนค่าลิสต์ที่ได้

lia = [[['a','b'],['c','d']],[['e','f'],['g',['h','i']]],['j','k'],'l']
print(yup(lia))

ในนี้จะเห็นว่าฟังก์ชัน yup มีการเรียกใช้ตัวมันเองในกรณีที่สมาชิกเป็นลิสต์ เพื่อให้ลิสต์นั้นยุบก่อนที่จะบวกเพิ่มเข้าไป ถ้าภายในลิสต์นั้นมีลิสต์อยู่อีกจึงทำการเรียกตัวเองซ้ำอีก

ปัญหานี้ยากที่จะใช้การวนซ้ำด้วย for เฉยๆโดยไม่ทำเป็นฟังก์ชันเวียดเกิด เพราะเราไม่รู้ว่าจะต้องมีวังวนซ้อนอยู่กี่ชั้น



หอคอยฮานอย

ตัวอย่างปัญหาอีกอย่างที่ดูเหมือนจะยากแต่ถ้าใช้ฟังก์ชันเวียนเกิดจะดูแล้วง่ายลงไปทันที



รายละเอียดเขียนไว้ใน https://phyblas.hinaboshi.com/20160301