สืบเนื่องจากบล็อก TECHJAM 2018 — Code Incubation #1 ที่ได้กล่าวถึงลักษณะรูปแบบการเขียน Recursive Function ในภาษาต่างๆ

Team AquaBlitz11 (ซึ่งประกอบด้วยผมเพียงคนเดียว o_o”) เห็นว่ายังมีประเด็นที่น่าสนใจมากมายเกี่ยวกับ Recursion จึงอยากจะนำมาเล่าเพิ่มเติม เพื่อเปลี่ยนความคิดของหลายๆ คนที่รู้สึกว่า Recursion เป็นเรื่องยาก ไม่สามารถนำมาใช้แก้ปัญหาต่างๆ ได้อย่างเป็นธรรมชาติ

Table of Contents

• What is “Recursion Fairy”?
  • Countdown from $N$ to $1$
  • Factorial Function
  • Tower of Hanoi
• The Recursive Ritual
  • Step 1 — นิยามฟังก์ชันให้ชัดเจน
  • Step 2 — หาวิธีการจัดการกับปัญหาแบบง่ายๆ
  • Step 3 — เช็คงานที่ส่งให้ Recursion Fairy ให้ดีๆ
  • Step 4 — Code!
• The End — What’s up next?

What is “Recursion Fairy”?

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

คนๆ นั้น (ฟังก์ชัน) จะมีกระบวนการคิดแบบนี้

• ถ้าปัญหานั้นมีขนาดเล็กพอที่พอทำได้ ก็ทำให้เสร็จไปเลย

• ถ้าปัญหานั้นมีขนาดใหญ่ แต่เราขี้เกียจ ให้เราทำแค่ขั้นเดียวพอ ส่วนปัญหาที่เหลือให้โยนให้ใครก็ได้ทำ

Q: “ใครก็ได้” ที่ว่านี่คือใคร?

A: ร่าง clone ของตัวเอง (ฟังก์ชันเดิม) นี่แหละ

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

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

คำหนึ่งที่ใช้เรียก “คนอื่น” ที่ว่านี้ก็คือ “Recursion Fairy” ที่มีความสามารถในการแก้โจทย์ปัญหาได้ด้วยพลังวิเศษอะไรสักอย่างที่เราไม่อาจรู้ได้ (เอาจริงๆ ก็รู้ได้ แต่มันจะทำให้งง) แต่รู้แค่ว่า เมื่อให้ Recursion Fairy จัดการให้แล้ว งานจะเสร็จสิ้นตามที่เรากำหนดไว้อย่างแน่นอน

เพียงแค่เราศรัทธาในเทพธิดาแห่ง Recursion ชีวิตการเขียนโปรแกรมของเราก็จะง่ายขึ้นเป็นอย่างมาก

Countdown from $N$ to $1$

หากเราต้องการเขียนโปรแกรมที่จะนับเลขจาก $N$ ย้อนลงมาถึง $1$: วิธีหนึ่งที่เราทำได้ก็คือการเขียน Loop Iteration ไปเลย แต่อีกวิธีหนึ่งคือการสังเกตว่าการนับมันมีลักษณะอย่างไรกันแน่

สมมติว่าเราต้องการนับเลขจาก 10 ถึง 1 เราจะนับได้ว่า

10 9 8 7 6 5 4 3 2 1

แต่ถ้าเราสังเกตดีๆ เราสามารถมองได้ว่า มันคือการนับเลข 10 ก่อนเพียงตัวเดียว ส่วน 9 8 7 6 5 4 3 2 1 มองว่ามันคือการ “นับเลขจาก 9 ถึง 1”

การนับเลขจาก 9 ถึง 1 ที่มีผลเป็น

9 8 7 6 5 4 3 2 1

เราสามารถมองได้ว่ามันคือการนับเลข 9 ก่อนเพียงตัวเดียว ส่วน 8 7 6 5 4 3 2 1 มองว่ามันคือ “การนับเลขจาก 8 ถึง 1”

หากพูดในรูปแบบทั่วไปก็คือ การนับเลขจาก $N$ ถึง $1$ ให้นับเลข $N$ ก่อนเพียงตัวเดียว ส่วนเลข $N - 1, N - 2, …, 1 $ สามารถมองว่าเป็นปัญหาใหม่ได้ แต่ปัญหาใหม่นั้นมีรูปแบบคล้ายๆ ปัญหาเดิม เพียงแค่มีขนาดเล็กลงเท่านั้น

ดังนั้น เมื่อนำมาเขียนฟังก์ชัน countdown แทนที่จะเขียนว่า

for i = N down to 1:
    print i

เราสามารถเขียนได้ว่า

print(N)
countdown(N-1)

โดยให้เราเชื่อใจว่าการเรียกฟังก์ชัน countdown(N-1) ของเราจะทำงานถูกต้องโดยที่เราไม่ต้องไปสนใจเลยว่ามันจะเรียกฟังก์ชันซ้อนตัวเองต่ออะไรอย่างไร

ทั้งนี้ ต้องอย่าลืมกรณีที่ง่ายที่สุด นั่นก็คือกรณีที่ $N = 0$ เราไม่จำเป็นต้องนับอะไรเลย ให้ return ออกฟังก์ชันได้เลย มิเช่นนั้น ฟังก์ชัน countdown ของเราจะขี้เกียจมากเกินไป ลดขนาดปัญหาเรื่อยๆ จนปัญหามีขนาดติดลบลงไปเรื่อยๆ ไม่รู้จบ

Factorial Function

จากนิยามทางคณิตศาสตร์ \(N! = N \times (N-1) \times (N-2) \times \dots \times 1\)

โดยปกติเราจะเขียนฟังก์ชัน factorial ดังนี้

def factorial(N):
    ans = 1
    for i in range(N, 0, -1):
        ans *= i
    return ans

แต่เราจะนำความรู้เรื่อง Recursion มาใช้ โดยสังเกตจากกรณีตัวอย่าง

หากเราสังเกตดีๆ จะพบว่าส่วน $4 \times 3 \times 2 \times 1$ ความจริงแล้วมันคือ $4!$ นั่นเอง ดังนั้น จะเขียนได้ว่า

หรือหากเขียนในรูปทั่วไป จะได้ว่า

โดยส่วนที่เป็น $(N - 1)!$ เราไม่ต้องสนใจเลยว่าพื้นฐานจริงๆ มันคืออะไร ให้สมมติว่าเราสามารถคำนวณค่าของ $(N - 1)!$ ได้ถูกต้องเสมอ ส่วนกรณีที่ง่ายที่สุดก็คือ $0! = 1$

ดังนั้น แทนที่จะเขียนโค้ด Loop Iteration แบบเดิม เราสามารถเขียนเป็น Recursive Function ได้ดังนี้

def factorial(N):
    if N == 0:
        return 1
    return N * factorial(N-1)

จบ! :D

การทำงานจริง ๆ ของ Recursion Fairy (Animation จาก MathWarehouse)

Tower of Hanoi

มีเสาอยู่ 3 ต้น (สมมติว่ามันคือเสา $A$, $B$, $C$ ละกัน) และก็มีจานที่มีรูตรงกลางอยู่ $N$ ใบ สอดไว้ในเสา $A$ โดยมีขนาดเรียงจากใหญ่ไปเล็ก จากด้านล่างขึ้นสู่ข้างบน

เราต้องการย้ายจานทั้ง $N$ ใบ จากเสา $A$ ไปเสา $C$ โดยมีเงื่อนไขดังนี้

• เลื่อนจานได้แค่ครั้งละ 1 ใบเท่านั้น การเลื่อนทำได้โดย “ยกจานขึ้นออกจากเสา นำจานไปวางไว้ที่เสาอื่น (หากมีจานอื่นอยู่ที่เสานั้นอยู่แล้วก็ให้วางทับไปข้างบน)”

• หากมีจานวางซ้อนกัน จานที่อยู่ข้างบนต้องมีขนาดเล็กกว่าจานข้างล่าง

รูปภาพจาก Wikipedia

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

ก่อนอื่น ขอกำหนดให้กระบวนการ Solve(N, A, B, C) หมายถึงการย้ายจาน $N$ ใบ ที่อยู่บนสุดของเสา $A$ ไปยังเสา $C$ โดยยังคงลำดับเดิมไว้อยู่ ด้วยวิธีการที่ไม่ขัดกับเงื่อนไขที่ระบุไว้ข้างต้น เช่น

• Solve(4, 'x', 'y', 'z') คือการเลื่อนจาน 4 ใบ จากเสา x ไปยังเสา z โดยที่เราอนุญาตให้ใช้เสา y ช่วยได้

• Solve(5, C, A, B) คือการเลื่อนจาน 5 ใบ จากเสาที่มีชื่อตามตัวแปร $C$ ไปยังเสาที่มีชื่อตามตัวแปร $B$ โดยอนุญาตให้ใช้เสาที่มีชื่อตามตัวแปร $A$ ช่วยได้

(สังเกตว่าตัวแปร $C$, $A$, $B$ ในตัวอย่างที่ 2 เป็นตัวแปรที่เรานำมาใช้เก็บชื่อเสาเริ่มต้น เสาสิ้นสุด และก็เสาช่วยเท่านั้น ไม่ได้เกี่ยวกับการนิยามฟังก์ชันที่เรียงลำดับเป็น $A$, $B$, $C$ แต่อย่างใด ในส่วนของนิยามฟังก์ชันเราอาจจะนิยามเป็นตัวอักษรอื่นก็ได้ เราแค่ตั้งชื่อเพื่อความสะดวกในการเขียนโค้ดเฉย ๆ)

ในการ Solve(N, A, B, C) ให้เรามองปัญหาในมุมมองของจานใบที่อยู่ล่างสุดของเสา $A$ ว่า การที่จะเลื่อนจานใบล่างสุดได้นั้น เราจำเป็นต้องย้ายจานที่อยู่ข้างบนทั้งหมดไปไว้ที่เสา $B$ ก่อน เราจึงจะย้ายใบสุดท้ายจากเสา $A$ ไปเสา $C$ ได้ หลังจากนั้นจึงค่อยย้ายใบที่ไปฝากไว้ที่เสา $B$ กลับมาทับคืนบนเสา $C$

เขียนให้ชัดเจนขึ้นได้ดังนี้

• เราต้องเลื่อน $N - 1$ ใบ ที่อยู่ข้างบนเสา $A$ ไปไว้ที่เสา $B$ ก่อน (หากจำเป็นต้องใช้เสาอื่นช่วย ให้ใช้เสา $C$)

• เลื่อนใบสุดท้ายนี้ไปเป็นฐานของเสา $C$

• เลื่อน $N - 1$ ใบ ที่อยู่บนเสา $B$ ไปทับคืนที่เสา $C$ (หากจำเป็นต้องใช้เสาอื่นช่วย ให้ใช้เสา $A$)

Animation จาก Wikipedia

เราอาจจะรู้สึกอยากลองคิดต่อว่าการย้ายจาน $N - 1$ ใบนั้น จะทำอย่างไร แต่ความจริงแล้วเราไม่จำเป็นต้องพยายามคิดถึงรายละเอียดจริงๆ เลย ศรัทธาในพลังของเทพธิดาแห่ง Recursion หรือ Recursion Fairy ก็เพียงพอแล้ว

ถึงอย่างไรก็ตาม อย่าลืมกรณีที่ง่ายที่สุด (มิเช่นนั้นขนาดปัญหาของเราจะโดน -1 ไปเรื่อยๆ จนในที่สุดก็ติดลบไม่รู้จบ) โดยสำหรับข้อนี้กรณีง่ายสุดจะอยู่ที่ $N = 0$ ซึ่งไม่จำเป็นต้องทำอะไรเลย

def move(A, B):
    print("move disc from peg", A, "to peg", B)
def solve(N, A, B, C):
    if N == 0:
        return
    solve(N-1, A, C, B)
    move(A, C)
    solve(N-1, B, A, C)

The Recursive Ritual

ถึงแม้ว่าเทพธิดาแห่ง Recursion จะช่วยให้เราเข้าใจการแก้ปัญหาแบบ Recursive ได้ง่ายขึ้น การที่เราเอาแต่อ้อนวอนขอให้มีเทพมาช่วยทำให้ผลการ submit โค้ดของคุณเปลี่ยนจาก “Wrong Answer” เป็น “Correct” ดูจะไม่เหมาะสม ดังนั้นเราจึงต้องศึกษาว่าเทพธิดาแห่ง Recursion คาดหวังให้เราทำอะไรบ้างกันแน่จึงจะได้รับพรศักดิ์สิทธิ์จากเทพธิดาองค์นี้

Step 1 — นิยามฟังก์ชันให้ชัดเจน

การที่จะแก้โจทย์เกี่ยวกับ recursion ได้นั้น เราจะต้องนิยามฟังก์ชันที่เราจะใช้แก้ปัญหาให้ชัดเจนก่อน ว่าความคาดหวังของเรากับฟังก์ชันนั้นคืออะไรกันแน่ ในตัวอย่าง Tower of Hanoi เราได้นิยามฟังก์ชัน Solve ไว้อย่างชัดเจน ดังนี้

ขอกำหนดให้กระบวนการ Solve(N, A, B, C) หมายถึงการย้ายจาน $N$ ใบ ที่อยู่บนสุดของเสา $A$ ไปยังเสา $C$ โดยยังคงลำดับเดิมไว้อยู่ ด้วยวิธีการที่ไม่ขัดกับเงื่อนไขที่ระบุไว้ข้างต้น

เมื่อเรานิยามฟังก์ชันไว้อย่างชัดเจนแล้ว เทพธิดาแห่ง Recursion ก็จะเข้าใจว่าเราต้องการอะไร เมื่อเทพธิดาเข้าใจแล้ว หน้าที่ของเราคือแสดงให้เห็นว่าเรามีความพยายาม สามารถทำงานได้ด้วยตนเอง แม้ว่าจะทำได้แค่เพียงขั้นตอนเดียวก็ตาม Step 2 ก็คือ

Step 2 — หาวิธีการจัดการกับปัญหาแบบง่ายๆ

ฟังก์ชัน Recursion จะประกอบด้วยสองส่วนคือ

• Base Case — ปัญหาในกรณีที่ง่ายที่สุด สามารถแก้ไขได้เลยโดยไม่ต้องพึ่ง Recursion Fairy

• Recursive Step — ปัญหาที่เราไม่สามารถแก้ได้ง่ายๆ หน้าที่ของเราคือลดขนาดปัญหาลงเพียงเล็กน้อย แล้วส่งให้ Recursion Fairy จัดการ

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

Step 3 — เช็คงานที่ส่งให้ Recursion Fairy ให้ดีๆ

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

ยกตัวอย่าง ในปัญหา Tower of Hanoi เราควรถามตัวเองว่า

มั่นใจได้ไงว่าวิธีลดขนาดงานที่เรากำหนดไว้ จะไม่ทำให้ Recursion Fairy เผลอเอาจานใหญ่วางบนจานเล็ก

การพิสูจน์คร่าวๆ สามารถทำได้โดยสังเกตว่า ก่อนเรียกฟังก์ชัน solve(N, A, B, C) เรา assume ลักษณะของจาน/เสาดังนี้

• มีจานอย่างน้อย $N$ ใบ บนเสา $A$ โดยจาน $N$ ใบบนสุดมีขนาด $1, 2, 3, \dots, N$ ตามลำดับจากบนลงล่าง (ห้ามมีขนาด $1, 2, 4, 5 $ เป็นต้น เพราะระหว่างการย้ายเราอาจจะเผลอนำจาน 4–5 ไปวางทับจาน 3 ที่เสาอื่นได้)

• จานที่ซ้อนอยู่แล้วในแต่ละเสาไม่ขัดเงื่อนไข “จานเล็กวางบนจานใหญ่”

สังเกตว่า ในแต่ละขั้นตอนของเรา ฟังก์ชันเราจะไม่ผิดจากเงื่อนไข ตัวอย่างเช่น ขั้นตอนแรก solve(N-1, A, C, B) ให้สังเกตว่าก่อนการเรียกฟังก์ชันนี้ตรงตามเงื่อนไขสองข้อที่เรากำหนดไว้ คือมีจาน $N - 1$ ใบบนเสา $A$ และจานยังคงเรียงถูกต้องอยู่ (เพราะเรายังไม่ได้ทำอะไรเลย)

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

เมื่อพิสูจน์ความถูกต้องแล้ว จึงเริ่มลงมือ…

Step 4 — Code!

การเขียน Recursive Function สามารถเขียนได้คล้ายๆ กับการเขียนฟังก์ชันปกติเลย ไม่ได้มี syntax อะไรพิเศษไปกว่าการประกาศฟังก์ชันปกติ แค่มีส่วนที่เรียกฟังก์ชันเป็นชื่อตัวเองซ้ำเท่านั้น

เพราะฉะนั้นถ้าเราคิดรายละเอียดฟังก์ชันของเราดีพอแล้ว การ implement ฟังก์ชันดังกล่าวก็ควรทำได้ในเวลาอันสั้น

The End — What’s up next?

ในการเขียนโปรแกรมพื้นฐาน เราอาจจะเห็นว่า Recursion ไม่ได้สำคัญมากนัก แต่หากศึกษาเกี่ยวกับ Algorithms และ Data Structures ลึกเข้าไปแล้ว จะพบว่า Recursion คือหัวใจของทุกๆ สิ่ง

เมื่อเข้าใจหลักการของ Recursion แล้วก็จะช่วยให้เราสามารถศึกษาเรื่องอื่นได้เข้าใจมากยิ่งขึ้น เช่น การทำ Depth-first Search บนกราฟ (หรือบนต้นไม้), memoization (Dynamic Programming), การเขียน Binary Search Tree เป็นต้น

เพราะฉะนั้น อย่าลืมฝึกทำโจทย์ Recursion กันเยอะๆ นะครับ และก็เพื่อเป็นการรักษาขนบธรรมเนียมประเพณีอันดีงามของชาวไทย อย่าลืมตอบแทนบุญคุณของเทพธิดาแห่ง Recursion — Recursion Fairy ที่คอยทำงานต่างๆ ให้เราด้วยการไม่เขียนโค้ดบัคให้เทพธิดาปวดหัวด้วยนะครับ เพียงแค่นี้ทุกฝ่ายก็น่าจะสบายใจแล้ว