Recuper เทคนิคการวาดรูปด้วย Recursive
สืบเนื่องจากบล็อก TECHJAM 2018 — Code Incubation #1 ที่ได้กล่าวถึงลักษณะของ Recursion ในการเขียนโปรแกรม
ทางทีม PlugFire จึงขอมาเล่าตัวอย่างดี ๆ เสริมเพิ่มเติมเกี่ยวกับ Recursion ในด้านความสะดวกสบายมากกว่าการใช้เฉพาะการทำซ้ำ(Repeat) และมีจุดประสงค์เพื่อให้ผู้ที่กำลังศึกษาเรื่องนี้ที่กำลังท้อแท้ ได้เปิดใจเรียนรู้ และหลงไหลในมัน
เกริ่น
ถ้าพูดถึงปัญหาการปริ้นแสดงตัวอักษรบนหน้าต่าง console ดำ ๆ ที่เกิดจากการเขียนโปรแกรมด้วยภาษาคอมพิวเตอร์อย่างมีรูปแบบที่ชัดเจนและเป็นระเบียบนั้น คำศัพท์ที่สื่อถึง การปริ้นแสดงผลให้เป็นรูปร่างนี้ เราเรียกว่า การวาด(Drawing) และเรียกปัญหาการวาดอย่างมีรูปแบบว่า Pattern Problem
สำหรับผู้ที่เขียนโปรแกรมโดยทั่วไปแล้ว พวกเรามักจะคิดว่า การใช้วงวน หรือที่เรียกกันว่า Loop นั้น สามารถนำมาโค้ดเพื่อแก้ Pattern Problem นี้แสนจะสะดวกสะบาย เพราะมันเข้าใจง่าย และไล่เรียงลำดับการคิดคำนวณอย่างเป็นลำดับได้ การวาดด้วยวิธีนี้จึงเข้าใจได้ไม่ยาก
ตัวอย่างเช่น การวาดรูปพีระมิดสามเหลี่ยมชนิดหนึ่งที่มีความสูงสอดคล้องกับเลขข้อมูลนำเข้าดังตัวอย่างภาพที่ 1 นี้
เราสามารถนึกถึงการวาดรูปดังกล่าวได้ในรูปแบบของแถวและคอลัมน์ตามลำดับ ทำให้ได้โค้ดประมาณนี้
ซึ่งโค้ดดังกล่าว ไม่ได้ลำบากต่อการทำความเข้าใจเรื่องของลำดับการแสดงผลจากแนวซ้ายไปขวา แล้วต่อด้วยแนวบนลงล่างเลยแม้แต่น้อย เพียงใช้เวลาทดเลขสักพักก็จะเห็นถึงรูปแบบที่สอดคล้องกันแล้ว การวาดจากแนวซ้ายไปขวา และต่อด้วย แนวบนลงล่างนี้ เรียกว่า LRUD-chain drawing
แต่บางปัญหาของ Pattern Problem ก็ไม่สามารถแสดงผลจากแนวซ้ายไปขวา แล้วบนลงล่างได้โดยตรง เพราะการวาดรูปตามแนวคิด LRUD-chain drawing นั้น มันเป็นการสร้างข้อจำกัดโดยใช่เหตุด้านการวาดภาพที่สบาย เพราะมันจะวาดได้เพียงภาพที่พยายามจะไม่ยกพู่กัน ในขณะที่บางภาพ มันก็อาจต้องถูกแต่งเติมสีที่แต่งต่างกัน รูปแบบที่แตกต่างกันได้ ความซับซ้อนที่เกิดขึ้นนี้เอง การใช้ Loop มาวาดอาจจะกระทำได้อย่างยากลำบาก
แล้วจะใช้อะไรมาวาดล่ะ ดังนั้นใน blog นี้ขอนำเสนอการวาดภาพที่ใช้กระดาษมาช่วย โดยขอกำหนดให้การแสดงผลทางหน้าจอคือ ภาพวาดผลลัพธ์ (Output) และกำหนดให้กระดาษก็คือ Array 2 มิติ โดยเราจะใช้ Recursive เป็นพู่กัน นำแต่งแต้มสีลงบนกระดาษ เราจะนำภาพที่แต่งแต้มเสร็จสรรพแล้วนั้นไปเป็นภาพวาดผลลัพธ์นั่นเอง เราเรียกเทคนิดการใช้ Recursive วาดภาพลงบนกระดาษ (Paper) แบบนี้ว่า Recuper หรือบางครั้งก็เรียกว่า Illustration of Recursion
แล้ว Recursive จะมาวาดรูปลงบนกระดาษอย่างไรล่ะ เราจะขออธิบายด้วยการยกตัวอย่างดีกว่า
เนื้อหา
ขอนำเสนอปัญหาที่ชื่อว่า การวางกระเบื้องอลเวง
ให้ n เป็นจำนวนเต็มบวก เราจะมาปูสนามขนาด 2^n x 2^n ตารางหน่วย ด้วยกระเบื้องลวดลายต่าง ๆ ดังภาพตัวอย่างที่ 2 ให้จัดกระเบื้องอย่างไรก็ได้ให้เหลือพื้นที่วางไว้เพียงแค่ 1 x 1 ตารางหน่วยที่ตำแหน่ง (x, y) เท่านั้นเนื่องจากเป็นโจทย์เขียนโปรแกรมแข่งขัน(Competitive Programming) ดังนั้นขอกำหนดขอบเขตข้อมูล(Constraints)ดังนี้1 <= n <= 101 <= x, y <= 2^n โดยพิกัด (1, 1) คือมุมซ้ายบนของตาราง และ (1, 2^n) คือมุมขวาบนของตารางตัวอย่างโปรแกรม (ทางด้านซ้ายมือจะเป็นผลลัพธ์ที่เห็น ทางด้านขวามือจะเป็นการจำลองการวางกระเบื้อง)
จากโจทย์ดังกล่าวนี้ เด็กมัธยมหลาย ๆ คนที่เรียนสายคณิตศาสตร์ (Gifted Math) คงจะคุ้นเคยกันดีกับลักษณะโจทย์นี้ ใช่แล้ว นี่คือโจทย์ตัวอย่างที่ใช้ในการพิสูจน์แบบอุปนัยเชิงคณิตศาสตร์ (Mathematical induction) ซึ่งเป็นการพิสูจน์ที่มีหลักการว่า ถ้าแสดงให้เห็นจริงได้ว่าที่จุดเริ่มต้นมีค่าเป็นจริงได้ นั่นคือ F(ค่าเริ่มต้น) เป็นจริง และมีความสัมพันธ์ว่า F(n) เป็นจริงแล้ว F(n+1) ก็จะเป็นจริงตาม กล่าวไดว่า F(n) ก็จะเป็นจริงในทุก ๆ จำนวนเต็ม n โดยที่ n >= ค่าเริ่มต้น
ซึ่งการแก้ปัญหาโจทย์การวางกระเบื้องอลเวงนี้ก็ใช้หลักการพิสูจน์อุปนัยมาเป็นแนวคิดเช่นกัน โดยขอแสดงบทพิสูจน์ตรงนี้
บทพิสูจน์. ขั้นแรก ต้องพิสูจน์กรณีเริ่มต้นให้ได้ก่อน นั่นคือกรณีที่ n = 1 เราจะเห็นได้ว่า (x, y) ที่เป็นไปได้คือ (1, 1), (1, 2), (2, 1), (2, 2) ซึ่งไม่ว่าจะเป็นอะไร เราก็สามารถวางกระเบื้องลวดลายต่าง ๆ ได้เสมอ ดังนั้นกล่าวได้ว่าเมื่อ n = 1 ทำให้สามารถวางกระเบื้องโดยมีพื้นที่ว่างเหลือ 1 x 1 ตารางหน่วยได้เสมอ เป็นจริงต่อมาในขั้นตอนอุปนัย หรือก็คือการพิสูจน์ให้ได้ว่า เมื่อ F(n) เป็นจริงแล้วจะทำให้ F(n+1) เป็นจริงกำหนดให้ F(n) คือข้อความที่ว่าสามารถวางกระเบื้องตามที่กำหนดลงบนสนามขนาด 2^n x 2^n ตารางหน่วยโดยเหลือช่องว่างพื้นที่ขนาด 1 x 1 ตารางหน่วยพอดี เราจะแสดงให้เห็นจริงว่าถ้า F(n) เป็นจริงแล้ว เราจะสามารถวางกระเบื้องบนสนามขนาด 2^(n+1) x 2^(n+1) ตารางหน่วยได้เช่นกันวิธีนั้นแสนเรียบง่าย โดยจะขอใช้ภาพต่อไปนี้อธิบาย
จากภาพ ก้อนสี่เหลี่ยมดำ ๆ ที่แยกออกมา ด้านซ้ายบนนั่นคือ ช่องว่างที่กระเบื้องลงไม่ได้ขนาดพื้นที่ 1 x 1 ตารางหน่วยอยู่ที่พิกัด (x, y) ส่วนก้อนสี่เหลี่ยมดำ ๆ สามก้อนที่อยู่ตรงกลาง ๆ ภาพนั่นคือ กระเบื้องที่เราจะวาง ส่วนเหตุที่ใช้กระเบื้องแบบไม่มีลวดลายนั่นก็เพราะ เราสามารถหมุนก้อนสามก้อนนี้ให้เป็นรูปกระเบื้องลวดลายชนิดอื่น ๆ ได้ต้องการนั่นเองจากภาพ เราจะสร้างสนามพื้นที่ขนาด 2^(n+1) x 2^(n+1) ตารางหน่วย เราสามารถทำการแบ่งสนามออกเป็น 4 ส่วนโดยมีพิกัดต่าง ๆ ดังภาพตัวอย่างที่ 4 แล้ววางกระเบื้องตามภาพ โดยสนามที่แบ่งไปแต่ละส่วนก็จะมีขนาด 2^n x 2^n ตารางหน่วย ซึ่งเราสามารถมองว่า ก้อนสี่เหลี่ยมดำ ๆ แต่ละก้อนก็คือ พื้นที่ ๆ จะไม่มีกระเบื้องมาวางแน่นอน จะเห็นได้ว่า เมื่อแบ่งและวางตามนี้แล้ว ทำให้แต่ละก้อนที่แบ่ง สอดคล้องกับข้อกำหนดของ F(n) ที่เรากำหนดให้เป็นจริงไว้ก่อนแล้ว ดังนั้น สนามทั้ง 4 ส่วนที่ถูกแบ่งก็จะสามารถเติมกระเบื้องได้เต็มพอดี จากหลักการแห่งอุปนัยคณิตศาสตร์ เราสรุปได้ว่าสามารถวางกระเบื้องลวดลายต่าง ๆ บนสนามขนาด 2^n x 2^n ตารางหน่วย โดยเหลือพื้นที่ 1 x 1 ตารางหน่วยที่พิกัด (x, y) ใด ๆ ได้เสมอ .
จากการพิสูจน์นี้ มองมันไปเป็นเรื่องการวาดรูปที่เราเคยกล่าวมา กระดาษก็คือสนาม กล่าวได้ว่า หากจะวาดรูปกระเบื้องลงบนกระดาษขนาด 2^n x 2^n แล้วหลักการก็คือ แบ่งกระดาษออกเป็น 4 ส่วนขนาดเท่ากัน พื้นขนาด 1 x 1 ตารางหน่วยที่อยู่พิกัด (x, y) ต้องอยู่ที่กระดาษส่วนใดส่วนหนึ่งใน 4 ส่วนนั้น เราก็ทำการวาดต่อในส่วนที่มี (x, y) อยู่ แล้วทำการวาดอีกสามส่วนที่เหลือด้วยพิกัด (x, y) ใหม่ที่สอดคล้องกับกระเบื้องที่จะวางสามช่อง
จากหลักการคิดแบบนี้ สามารถนำมาเขียน Recursive ได้ เพียงแต่การเขียน Recursive ในลักษณะนี้ จะเป็นการนำความจริงที่ถูกต้องตามหลักคณิตศาสตร์มาเขียนเฉย ๆ ดังนั้นมันจึงเป็นการคิดในลักษณะที่ว่า ถ้าการเรียกคำสั่งแบบนี้ถูกต้องแน่นอนละ เราจะเขียนอะไรต่อให้มันถูกต้องอีก หากทำสิ่งเหล่านี้ได้ จะได้ว่า Recursive ของเราจะทำงานได้อย่างถูกต้องแล้วนั่นเอง
เริ่มต้นเขียนโปรแกรม
เราจะได้หน้าตาโปรแกรมโดยรวมตามภาพตัวอย่างที่ 5 นี้ โดยเราจะใช้เทคนิค Recuper ดังนั้นก็ต้องเตรียมกระดาษโดยการจอง Array ไว้เท่าที่จะใช้ เนื่องจากตัวอย่างนี้ n มีค่ามากสุดคือ 10 จะได้ตารางมากสุดขนาด 1024 x 1024 แต่เราจะทำการจองเผื่อไว้เป็นเทคนิคการใช้ memory ไม่ให้บัค โดยสิ่งที่เราจะทำต่อมานั่นคือ การเขียนฟังก์ชัน draw นั่นเอง
เนื่องจากฟังก์ชัน draw() จะเป็น function Recursive ดังนั้น เราจะมานิยามรูปแบบที่แน่นอนให้กับฟังก์ชันที่จะใช้กันก่อน โดยรูปแบบต่อไปนี้เป็นรูปแบบที่คล้าย ๆ กันกับปัญหาอื่น ๆ ที่จะใช้เทคนิค Recuper ในการแก้
นั่นคือ การกำหนดขอบเขตของกระดาษที่ลงวาดผ่านพิกัดมุมของกระดาษ 2 พิกัด ซึ่งจริง ๆ แล้วจะใช้พิกัดมุมไหนก็ได้ แต่โดยความนิยมเราจะใช้ พิกัดมุมซ้ายบน และพิกัดมุมขวาล่าง เป็นตัวกำหนด ดังนั้นฟังก์ชัน draw() ของเราต้องมี parameter อย่างน้อยสี่ตัวแล้ว เพื่อสื่อถึงพิกัด 2 พิกัดดังกล่าว จะได้ว่าฟังก์ชัน void draw(int r1, int c1, int r2, int c2, …) หมายถึงฟังก์ชันที่จะวาดรูปลงบนกระดาษตั้งแต่พิกัดมุมซ้ายบนที่ (r1, c1) ถึงมุมขวาล่างที่พิกัด (r2, c2) ดังนั้นเวลาเรียกใช้ฟังก์ชันนี้ ค่า parameter เริ่มต้นก็คือ เราจะวาดรูปตั้งแต่พิกัด (1, 1) ถึง (2^n, 2^n) การเรียกก็จะเป็น draw(1, 1, 1 << n, 1 << n); หมายเหตุ 1 << n หมายถึง การเลื่อนเลข …00001 ในฐาน 2 ไปด้านซ้าย n ครั้ง เช่น n = 3 จะได้ 1 << n เป็น …01000 ในฐาน 2 ซึ่งจะมีค่าเท่ากับ 8 ในฐาน 10 ดังนั้น 1 << n จึงเป็นการดึงค่า 2^n ออกมาจากคอมพิวเตอร์นั่นเอง
ต่อมาคือการกำหนดค่าความเป็นปัจจุบันให้ Recursive เนื่องจากทุก ๆ ครั้งที่ Recursive มีการเรียกฟังก์ชันตัวมันเอง ความเป็นอดีตจะเสียไป ดังนั้นต้องสร้างความเป็นปัจจุบันให้มันด้วย โดยตามปัญหาแล้ว เราจะต้องบอกพิกัดที่จะวางพื้นที่ว่าง (x, y) และตัวอักษรที่จะลง ณ ตำแหน่งช่องว่างนั้น จะทำให้เราได้ parameter มาอีก 3 ตัว ก็จะเพียงพอต่อการเขียนฟังก์ชัน Recursive ในตัวปัญหานี้แล้ว
ต่อมาคือการกำหนด Base Case หรือก็คือ การกำหนดการกระทำบางอย่างที่เราสามารถสรุปได้เลยในทันทีเมื่อไม่มีปัญหาที่เล็กกว่ากรณีนี้แล้ว หรือถึงจะมีปัญหาที่เล็กกว่ากรณี Base Case แต่ Base Case ก็จะสามารถตอบคำถามของปัญหาเล็ก ๆ เหล่านั้นได้หมด ซึ่งในตัวอย่างนี้ ปัญหาที่เล็กที่สุดที่เราสามารถตอบได้เลยทันทีก็คือ เมื่อกระดาษมีขนาด 1 x 1 ตารางหน่วยนั่นเอง จาก Parameter ทั้งหมดสามารถตอบได้เลยทันทีว่าต้องเต็มตัวอักษรที่รับเข้ามานั่นเอง เพราะ 1 ช่องที่เหลือก็คือพื้นที่ว่างที่จะไม่มีกระเบื้องชนิดอื่นมาเติมแล้วนั่นเอง จะได้โค้ดตามภาพตัวอย่างที่ 8
จากนั้นจะเป็นการคิดในกรณี Recursion หรือที่เรียกกันว่า การเรียกซ้ำ โดยตามหลักการที่เราจะทำ คือ การแบ่งกระดาษออกเป็น 4 ส่วนเท่ากัน ดังนั้น ก็ต้องคำนวณจุดกึ่งกลางระหว่างนั้นก่อน ก็แยกคิดเป็นแกนตั้งและแกนแนวนอนได้ โดยจุดแกนตั้งที่อยู่กึ่งกลางระหว่าง r1 กับ r2 จะได้ค่าเป็น (r1 + r2) / 2 ปัดเศษลงขอตั้งชื่อจุดนี้ว่า rm (ย่อมาจาก row mid ) ในทำนองเดียวกัน cm (column mid) ก็จะมีค่าเท่ากับ (c1 + c2) / 2 ปัดเศษลง ซึ่งพิกัด (rm, cm) นี้จะเป็นพิกัดมุมขวาล่างของสี่เหลี่ยมย่อยมุมซ้ายบนที่เราจะแบ่ง โดยในปัจจุบันของ Recursion ตอนนี้เราจะได้ภาพ ดังภาพตัวอย่างที่ 9
จากภาพ เราจะทำการเติมช่องดำ ๆ สามตัวที่ติดกันตามกรณีที่พิกัด (x, y) อยู่ โดยสามารถแยกออกเป็น 4 กรณีดังนี้
- กรณีที่ 1 เมื่อพิกัด (x, y) ไปอยู่มุมซ้ายบน สามารถตรวจสอบได้จากเงื่อนไขถ้า x <= rm and y <= cm ได้ เมื่อเงื่อนไขนี้เป็นจริง เราจะทำการวาดต่อในช่องซ้ายบนโดยเติมอักษร mark ที่พิกัด (x, y) จากนั้นวาดต่อที่ช่องขวาบน แล้วเติมต่อที่ช่องซ้ายล่างและจากนั้นปิดท้ายด้วยที่ช่องขวาล่างตามลำดับ เป็นโดยเติมเลข 4 เพราะเลขนี้คือลักษณะลวดลายที่สอดคล้องกับกรณีนี้ จะได้โค้ดดังนี้
draw(r1, c2, rm, cm, x, y, mark); //วาดต่อที่ช่องซ้ายบน โดยเติมตัวอักษร mark ที่พิกัด (x, y)
draw(r1, cm+1, rm, c2, rm, cm+1, '4'); //วาดต่อที่ช่องขวาบน โดยเติมเลข 4 ที่พิกัด (rm, cm+1)
draw(rm+1, c1, r2, cm, rm+1, cm, '4'); //วาดต่อที่ช่องซ้ายล่าง โดยเติมเลข 4 ที่พิกัด (rm+1, cm)
draw(rm+1, cm+1, r2, c2, rm+1, cm+1, '4'); //วาดต่อที่ช่องขวาล่าง โดยเติมเลข 4 ที่พิกัด (rm+1, cm+1)- กรณีที่ 2 เมื่อพิกัด (x, y) ไปอยู่มุมขวาบน สามารถตรวจสอบได้จากเงื่อนไขถ้า x <= rm and y > cm ได้ เมื่อเงื่อนไขนี้เป็นจริงเราก็จะทำทำนองเดียวกับกรณีที่ 1 เพียงแต่จะเป็นการวาดต่อที่ช่องขวาบนโดยเติมตัวอักษร mark ที่พิกัด (x, y) แล้วเติมเลข 3 ในช่องที่เหลือ จะได้โค้ดดังนี้
draw(r1, c1, rm, cm, rm, cm, '3'); //วาดต่อที่ช่องซ้ายบน โดยเติมเลข 3 ที่พิกัด (rm, cm)
draw(r1, cm+1, rm, c2, x, y, mark); //วาดต่อที่ช่องขวาบน โดยเติมตัวอักษร mark ที่พิกัด (x, y)
draw(rm+1, c1, r2, cm, rm+1, cm, '3'); //วาดต่อที่ช่องซ้ายล่าง โดยเติมเลข 4 ที่พิกัด (rm+1, cm)
draw(rm+1, cm+1, r2, c2, rm+1, cm+1, '3'); //วาดต่อที่ช่องขวาล่าง โดยเติมเลข 4 ที่พิกัด (rm+1, cm+1)- กรณีที่ 3 เมื่อพิกัด (x, y) ไปอยู่มุมซ้ายล่าง สามารถตรวจสอบได้จากเงื่อนไขถ้า x > rm and y <= cm ได้ เมื่อเงื่อนไขนี้เป็นจริงเราก็จะทำทำนองเดียวกับกรณีที่ 1 และ 2 เพียงแต่จะเป็นการวาดต่อที่ช่องซ้ายล่างโดยเติมตัวอักษร mark ที่พิกัด (x, y) แล้วเติมเลข 2 ในช่องที่เหลือ จะได้โค้ดดังนี้
draw(r1, c1, rm, cm, rm, cm, '2'); //วาดต่อที่ช่องซ้ายบน โดยเติมเลข 3 ที่พิกัด (rm, cm)
draw(r1, cm+1, rm, c2, rm, cm+1, '2'); //วาดต่อที่ช่องขวาบน โดยเติมเลข 4 ที่พิกัด (rm, cm+1)
draw(rm+1, c1, r2, cm, x, y, mark); //วาดต่อที่ช่องซ้ายล่าง โดยเติมตัวอักษร mark ที่พิกัด (x, y)
draw(rm+1, cm+1, r2, c2, rm+1, cm+1, '2'); //วาดต่อที่ช่องขวาล่าง โดยเติมเลข 4 ที่พิกัด (rm+1, cm+1)- กรณีที่ 4 เมื่อพิกัด (x, y) ไปอยู่มุมซ้ายล่าง สามารถตรวจสอบได้จากเงื่อนไขถ้า x > rm and y > cm ได้หรือตรวจสอบจากการไม่เข้าเงื่อนไหนเลยก็ได้ (else case) เมื่อเข้ากรณีนี้ได้เราก็จะทำทำนองเดียวกับกรณีที่ 1, 2 และ 3 เพียงแต่จะเป็นการวาดต่อที่ช่องขวาล่าง ดูโค้ดเลยดีกว่า
draw(r1, c1, rm, cm, rm, cm, '1'); //วาดต่อที่ช่องซ้ายบน โดยเติมเลข 3 ที่พิกัด (rm, cm)
draw(r1, cm+1, rm, c2, rm, cm+1, '1'); //วาดต่อที่ช่องขวาบน โดยเติมเลข 4 ที่พิกัด (rm, cm+1)
draw(rm+1, c1, r2, cm, rm+1, cm, '1'); //วาดต่อที่ช่องซ้ายล่าง โดยเติมเลข 4 ที่พิกัด (rm+1, cm)
draw(rm+1, cm+1, r2, c2, x, y, mark); //วาดต่อที่ช่องขวาล่าง โดยเติมตัวอักษร mark ที่พิกัด (x, y)ซึ่งจะได้โค้ดโดยรวมดังนี้
และเมื่อเราเขียน Recursion case ครบแล้ว ฟังก์ชันวาดรูปโดยใช้ Recursive ของเราก็เสร็จสรรพแล้วนั่นเอง ซึ่งโค้ดโดยรวมทั้งโปรแกรมจะได้ดังนี้
สรุป
จากตัวอย่างปัญหาการวางกระเบื้องอลเวงนี้ ทำให้เห็นได้ว่า การใช้ Recursion มาแก้ปัญหานั้น สามารถกระทำได้ใกล้เคียงกับภาษาธรรมชาติและสามัญสํานึกในการทำความเข้าใจ ด้วยเทคนิค Recuper นี้ถือเป็นท่าที่ดีอย่างหนึ่งของการใช้กระดาษที่ชื่อว่า Array และการแต่งแต้มสีต่าง ๆ ที่เรียกว่า Mathematical Induction ผ่านพู่กันที่ชื่อว่า Recursion ได้อย่างสวยงามและน่าหลงใหล(Magical)
