คำว่า recursion (การเรียกซ้ำ) มีความหมายสองอย่าง ซึ่งอาจทำให้สับสนได้ เนื่องจาก recursion มีบทบาทสำคัญในการอธิบายการคำนวณ จึงควรเข้าใจอย่างถ่องแท้ แม้ว่า recursion ในอัลกอริทึมจะสามารถแทนที่ด้วย loops ได้ แต่ recursion จริง ๆ แล้วเป็นแนวคิดที่พื้นฐานกว่า เพราะนอกจากจะใช้กำหนดการคำนวณแล้ว ยังใช้ในการนิยามข้อมูลด้วย การนิยามของ lists, trees และ grammars ล้วนต้องการ recursion; ไม่มีเวอร์ชันทดแทนที่อาศัย loops ดังนั้นหากต้องเลือกระหว่างสองแนวคิดนี้เพียงอย่างเดียว ควรเป็น recursion เพราะโครงสร้างข้อมูลจำนวนมากพึ่งพาแนวคิดนี้

คำว่า recursion มาจากคำกริยาในภาษาละติน recurrere ซึ่งมีความหมายคร่าว ๆ ว่า “วิ่งย้อนกลับ” คำว่า recursion จึงถูกใช้เพื่อบ่งชี้รูปแบบของความคล้ายตัวเอง (self-similarity) หรือการอ้างอิงถึงตัวเอง (self-reference) ความหมายทั้งสองนี้นำไปสู่แนวคิดเกี่ยวกับ recursion ที่ต่างกัน

ความคล้ายตัวเองพบได้ในภาพที่มีภาพของตัวเองในรูปขนาดย่อ เช่น ภาพของห้องที่มีทีวีซึ่งแสดงภาพเดิมของห้องนั้น รวมทั้งทีวีขนาดเล็กลงที่แสดงภาพซ้ำ ๆ ในทางตรงกันข้าม การอ้างอิงถึงตัวเองเกิดขึ้นเมื่อคำนิยามของแนวคิดนั้นมีการอ้างถึงตัวมันเอง โดยปกติผ่านการใช้ชื่อหรือสัญลักษณ์ ตัวอย่างเช่น พิจารณานิยามของคำว่า descendant (ซึ่งใช้เป็นฐานสำหรับอัลกอริทึมคำนวณ descendant ใน chapter 4) ลูกหลานของคุณคือบุตรของคุณทั้งหมดและลูกหลานของบุตรของคุณ ที่นี่ นิยามของคำว่า descendant รวมถึงการอ้างอิงถึงคำว่า descendant เอง

ในบทนี้ผมจะนำเสนอรูปแบบต่าง ๆ ของ recursion และอธิบายความสัมพันธ์ระหว่างรูปแบบความคล้ายตัวเองกับการอ้างอิงตัวเอง โดยใช้ภาพยนตร์ไตรภาค Back to the Future และแนวคิดการเดินทางข้ามเวลาเป็นตัวอย่างประกอบ การเดินทางข้ามเวลาสามารถมองได้ว่าเป็นกลไกที่ทำงานคล้าย recursion ในการบรรยายลำดับของเหตุการณ์ จากจุดเริ่มต้นที่สังเกตว่านิยามเชิง recursive สามารถเข้าใจได้เหมือนคำสั่งการเดินทางข้ามเวลา ผมจะอธิบายปัญหาพาราด็อกซ์ของเวลาและความสัมพันธ์กับการทำความเข้าใจนิยามเชิง recursive ผ่านแนวคิดของ fixed points.

บทนี้ยังชี้ให้เห็นคุณลักษณะหลายประการของ recursion ตัวอย่างเช่น การฝังภาพห้องในทีวีเป็น recursion แบบ direct ในความหมายที่ภาพของห้องถูกบรรจุเป็นส่วนหนึ่งของมันเองทันที ยิ่งไปกว่านั้น recursion ในตัวอย่างนี้เป็นแบบ unbounded หรือไม่จำกัด กล่าวคือการบรรจุนั้นดำเนินต่อไปเรื่อย ๆ จนไม่สิ้นสุด หากเราสามารถซูมเข้าและขยายหน้าจอทีวีให้เท่ากับภาพได้ซ้ำ ๆ เราจะไม่พบจุดสิ้นสุดของการบรรจุ บทนี้พิจารณาตัวอย่างของ recursion แบบ indirect และแบบ bounded และศึกษาผลกระทบของพวกมันต่อแนวคิดของ recursion

สุดท้าย ผมอธิบายความสัมพันธ์ใกล้ชิดระหว่าง loops กับ recursion โดยแสดงให้เห็นว่าอัลกอริทึมที่ใช้ loops เช่น อัลกอริทึมตามรอยก้อนหินของ Hansel และ Gretel สามารถอธิบายด้วย recursion ได้เช่นกัน ผมแสดงว่า loops และ recursion เทียบเท่ากัน หมายความว่าอัลกอริทึมใด ๆ ที่ใช้ loop สามารถแปลงเป็นอัลกอริทึมที่ให้ผลลัพธ์เดียวกันโดยใช้ recursion ได้เสมอ และในทางกลับกันก็เช่นกัน

เกี่ยวกับเวลา (It’s about Time)

เหมือนกับเรื่องราวการเดินทางข้ามเวลาเรื่องอื่น ๆ ภาพยนตร์ไตรภาค Back to the Future ใช้การเดินทางข้ามเวลาเป็นวิธีแก้ปัญหา แนวคิดทั่วไปคือระบุเหตุการณ์ในอดีตที่เป็นสาเหตุของปัญหาในปัจจุบันแล้วย้อนกลับไปเปลี่ยนเหตุการณ์นั้น โดยหวังว่าเหตุการณ์ต่อ ๆ ไปจะดำเนินไปต่างออกไปและหลีกเลี่ยงปัญหา ในเรื่อง Back to the Future นักวิทยาศาสตร์ Doc Brown ประดิษฐ์เครื่องย้อนเวลาในปี 1985 ซึ่งทำให้เขาและเพื่อน Marty McFly นักเรียนมัธยมได้เผชิญกับการผจญภัยหลายครั้ง ในภาคแรก Marty โดยบังเอิญย้อนกลับไปปี 1955 และเข้าไปขัดขวางการตกหลุมรักของพ่อแม่ของเขา ซึ่งเป็นภัยคุกคามต่อการดำรงอยู่ของเขาและพี่น้อง เขาสามารถฟื้นฟู (ส่วนใหญ่ของ) เส้นทางประวัติศาสตร์และกลับสู่ปี 1985 ได้อย่างปลอดภัย ในภาคที่สอง Marty, แฟนสาว Jennifer และ Doc Brown กลับมาจากการเดินทางไปปี 2015 ซึ่งพวกเขาต้องแก้ปัญหาเกี่ยวกับลูก ๆ ของ Marty และ Jennifer พวกเขาพบว่าในปี 1985 โลกกลับมืดมนและรุนแรงขึ้น โดยที่ Biff Tannen ฝ่ายตรงข้ามจากภาคแรกกลายเป็นคนร่ำรวยและมีอำนาจ Biff ฆ่าพ่อของ Marty และแต่งงานกับแม่ของเขา เขาสร้างความมั่งคั่งจากสมุดพยากรณ์ผลการแข่งขันกีฬา (sports almanac) จากปี 2015 ซึ่งทำนายผลการแข่งขันต่าง ๆ เขาขโมยสมุดเล่มนั้นจาก Marty ในปี 2015 และให้แก่ตัวเองในอดีตโดยเดินทางไปปี 1955 ด้วยความช่วยเหลือของเครื่องย้อนเวลา เพื่อคืนสภาพความเป็นจริงของปี 1985 ให้เหมือนเดิมก่อนที่พวกเขาจะไปปี 2015 Marty และ Doc Brown จึงย้อนกลับไปปี 1955 เพื่อลักสมุดพยากรณ์ของ Biff

Doc Brown: ชัดเจนว่า time continuum ถูกขัดจังหวะ ทำให้เกิดลำดับเหตุการณ์เชิงเวลาใหม่ที่ส่งผลให้เกิดความจริงทางเลือกนี้

Marty: พูดง่าย ๆ หน่อย Doc!

การกระโดดไปมาในกาลเวลาทั้งหมดนี้ฟังดูสับสนมาก และ Doc Brown ต้องอธิบายผลกระทบบางประการของการเดินทางที่วางแผนไว้ให้ Marty โดยใช้ภาพวาดบนกระดานดำ คล้ายกับแผนภาพที่ปรากฏทางด้านขวา

บางปัญหาในการทำความเข้าใจเรื่องราวการเดินทางข้ามเวลาเหล่านี้มีรากฐานมาจากประสบการณ์ของเราในการมองโลกเป็นเส้นเหตุการณ์เดียวที่มีอดีตและอนาคตเพียงหนึ่งเดียว ความเป็นไปได้ของการเดินทางข้ามเวลาเปิดประตูสู่ความเป็นไปได้ของความจริงทางเลือกหลายรูปแบบ อย่างไรก็ตาม การเดินทางข้ามเวลาและความจริงทางเลือกไม่ได้ไกลตัวเรามากนัก ก่อนอื่น เราทุกคนเดินทางผ่านกาลเวลาในชีวิตประจำวัน แม้จะจำกัดมาก หากอ้างอิงคำพูดของ Carl Sagan ว่า “We’re all time travelers—at a rate of exactly one second per second.” เรายังคิดถึงความเป็นไปได้ในอีกทางเมื่อวางแผนล่วงหน้าหรือรำลึกเหตุการณ์ในอดีต ถึงแม้เราไม่เคยสัมผัสความจริงทางเลือกเหล่านั้นโดยตรง

การเดินทางข้ามเวลาเป็นหัวข้อที่น่าหลงใหล แต่เกี่ยวข้องกับการคำนวณและโดยเฉพาะอย่างยิ่งกับ recursion อย่างไร? ดังที่แสดงโดยเรื่องเล่าและกิจกรรมประจำวันที่กล่าวมาข้างต้น การคำนวณหนึ่ง ๆ สอดคล้องกับลำดับของการกระทำที่คอมพิวเตอร์ (มนุษย์ เครื่องจักร หรือผู้กระทำอื่น ๆ) ทำ ดังนั้นการย้อนกลับไปในอดีตเพื่อทำการกระทำจึงเท่ากับการแทรกการกระทำนั้นเข้าไปในลำดับการกระทำที่นำไปสู่สถานะปัจจุบันของโลก เป้าหมายคือทำให้สถานะของโลกเป็นรูปแบบที่ต้องการเพื่อให้การกระทำบางอย่างสามารถทำได้ในปัจจุบัน

ตัวอย่างเช่น เมื่อ Marty, Jennifer และ Doc กลับจากปี 2015 มายังปี 1985 Marty คาดหวังว่าจะได้ไปตั้งแคมป์กับ Jennifer ตามแผน แต่สภาพโลกที่พวกเขาพบกลับไม่เอื้อให้เป็นไปได้ ดังนั้นพวกเขาย้อนอดีตและเปลี่ยนเหตุการณ์ด้วยการเอาสมุดพยากรณ์ของ Biff ออกไป เพื่อให้ลำดับการกระทำที่นำไปสู่ปัจจุบันสร้างสถานะที่พวกเขาคาดไว้ แต่การเดินทางข้ามเวลาไม่ได้จำกัดอยู่ที่ก้าวเดียวย้อนกลับเท่านั้น ทันทีหลังจากที่ Marty และ Doc Brown ทำภารกิจขโมยสมุดพยากรณ์แล้ว เครื่องย้อนเวลาก็ถูกฟ้าผ่าและพา Doc ไปปี 1885 ต่อมา Marty พบว่า Doc ถูกฆ่าหลังจากมาถึงปี 1885 ไม่กี่วัน โดยคนร้าย Buford “Mad Dog” Tannen ดังนั้นเขาย้อนกลับไป 1885 ตาม Doc โดยใช้เครื่องย้อนเวลาที่ Doc ซ่อนไว้ในเหมืองทองเก่าในปี 1885 เพื่อที่ Marty จะได้ไปค้นพบในปี 1955 ในปี 1885 เขาช่วย Doc ให้หลีกเลี่ยงการถูกยิงโดย Buford Tannen และสุดท้ายก็สามารถกลับไปปี 1985 ได้

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

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

เป็นตัวอย่างแรก ลองอธิบายการกระทำของ Marty ด้วยอัลกอริทึมแบบ recursive โดยเฉพาะ เราสามารถกำหนดอัลกอริทึม ToDo ผ่านสมการหลายสมการที่บอก Marty ว่าควรทำอะไรในเวลาใด:

ToDo(1985) = ToDo(1955); ไปตั้งแคมป์

ToDo(1955) = เอาสมุดพยากรณ์ผลการแข่งขันกีฬา; ToDo(1885); return to 1985

ToDo(1885) = ช่วย Doc หลีกเลี่ยง Buford Tannen; return to 1985

เราสามารถขยายอัลกอริทึมนี้ให้รวมการเดินทางไปปี 2015 ได้ แต่สามกรณีที่ยกมานี้ก็เพียงพอที่จะอธิบายประเด็นเกี่ยวกับ recursion ได้หลายข้อ ประการแรก สมการสำหรับ ToDo(1985) บอกว่าการกระทำที่ต้องทำในปี 1985 ต้องการการกระทำบางอย่างในปี 1955 เพราะเพื่อที่จะไปตั้งแคมป์กับ Jennifer โลกต้องอยู่ในสถานะที่เปลี่ยนไป ข้อกำหนดนี้ถูกแสดงโดยการใช้ recursion ในอัลกอริทึม ToDo หนึ่งในขั้นตอนของอัลกอริทึม ToDo คือการเรียกใช้อัลกอริทึม ToDo เอง ประการที่สอง การเรียกใช้อัลกอริทึมแบบ recursive ToDo(1955) ใช้อาร์กิวเมนต์ที่ต่างจากสมการของ ToDo(1985) ซึ่งเป็นส่วนหนึ่งของสมการนั้น นั่นหมายความว่า recursion จะไม่ทำให้เกิดการทำซ้ำที่เหมือนกันอย่างเป๊ะ ๆ (ต่างจากภาพห้องที่มีทีวี) และนี่มีความสำคัญต่อพฤติกรรมการยุติของการคำนวณ

ลองพิจารณาว่าการคำนวณจะดำเนินไปอย่างไรเมื่ออัลกอริทึมถูกรันด้วยอาร์กิวเมนต์ 1985 ขั้นตอนแรกของการคำนวณ ToDo(1985) คือการรัน ToDo(1955) ซึ่งหมายความว่าก่อนที่ Marty จะไปตั้งแคมป์ เขาต้องย้อนกลับไปปี 1955 เพื่อเอาสมุดพยากรณ์จาก Biff แต่ก่อนที่เขาจะกลับไป 1985 เขาต้องทำขั้นตอนที่ระบุใน ToDo(1885) นั่นคือเขาต้องย้อนกลับไปปี 1885 เพื่อช่วย Doc Brown หลังจากนั้นเขาจึงกลับมา 1985 เมื่อในที่สุดเขาก็สามารถไปตั้งแคมป์กับแฟนของเขาตามแผนได้

เมื่อตรวจดูสมการที่สามอย่างละเอียด เราสังเกตเห็นสิ่งที่ผิดปกติ แทนที่จะกลับไปยังปี 1955 ซึ่งเป็นเวลาที่ Marty มาจากเมื่อการคำนวณ ToDo(1885) เริ่มขึ้น อัลกอริทึมกลับสู่ปี 1985 โดยตรง นี่คือสิ่งที่เกิดขึ้นจริงในภาพยนตร์ภาคสาม ซึ่งสมเหตุสมผล เพราะการย้อนกลับไป 1955 แล้วจึงกลับไป 1985 ทันทีไม่น่าจะมีประโยชน์นัก (คนส่วนใหญ่ชอบเที่ยวบินตรงมากกว่าต่อเครื่อง)

อย่างไรก็ตาม พฤติกรรมนี้ไม่ใช่วิธีการทำงานของ recursion โดยทั่วไป เมื่อการคำนวณเชิง recursive เสร็จสิ้น มันจะกลับไปยังจุดที่ออกเดินทางไว้โดยอัตโนมัติ และการคำนวณจะดำเนินต่อไปทันทีข้างหลัง ณ ตัวอย่างนี้ มันจะหมายถึงการกระโดดไป 1885 แล้วกลับมาที่ 1955 สาเหตุของพฤติกรรมนั้นคือการคำนวณเชิง recursive โดยทั่วไปไม่รู้ว่าการคำนวณจะต่ออย่างไร ดังนั้นสิ่งที่ปลอดภัยคือการกลับไปยังจุดเริ่มต้นเพื่อไม่ให้พลาดสิ่งสำคัญ แม้ว่าสถานการณ์เฉพาะนี้ก้าวถัดไปคือการกลับไป 1985 การกระโดดโดยตรงก็ใช้ได้ เรื่องจะเป็นเรื่องประสิทธิภาพว่าควรมีสองกระโดดติดต่อกันหรือกระโดดเดี่ยว ใน Back to the Future เรื่องนี้สำคัญจริง ๆ เพราะ flux capacitor ที่ทำให้การเดินทางข้ามเวลาเป็นไปได้ต้องการพลังงานมากสำหรับแต่ละการกระโดด Doc Brown รำพึงถึงการออกแบบรถของเขาจากปี 1985:

ฉันจะประมาทได้อย่างไร? 1.21 gigawatts! Tom [Thomas Edison], ฉันจะผลิตพลังงานขนาดนั้นได้อย่างไร? มันทำไม่ได้ มันทำไม่ได้!

ไม่ว่าเมื่อไหร่ (No Matter When)

การใช้เครื่องย้อนเวลาของ Doc Brown ต้องระบุวันและเวลาที่แน่นอนของการเดินทาง แต่เนื่องจากวัตถุประสงค์ของการเดินทางข้ามเวลาคือการเปลี่ยนโซ่สาเหตุของเหตุการณ์ เวลา/วันที่ที่แน่นอนจึงไม่สำคัญตราบใดที่มาถึงก่อนเหตุการณ์ที่จะเปลี่ยน สมมติว่าเรามีตารางที่ประกอบด้วยวัน/เวลาของเหตุการณ์ทั้งหมดที่เราสนใจจะเปลี่ยน เราสามารถเขียนอัลกอริทึม ToDo แตกต่างออกไปโดยใช้การเปลี่ยนแปลงเชิงสาเหตุที่ตั้งใจไว้แทนการกระโดดเวลาที่เฉพาะเจาะจง แท้จริงแล้ว สไตล์การใช้การกระโดดตรงใน ToDo เป็นวิธีเก่า มันเหมือนกับวิธีที่ภาษาเครื่องระดับต่ำสำหรับโปรเซสเซอร์ทำงาน โดยการใส่ป้ายกำกับชิ้นส่วนของโค้ดแล้วใช้คำสั่ง jump เพื่อย้ายระหว่างชิ้นของโค้ด โครงสร้างการควบคุมทั้งหมดที่กล่าวถึงใน chapter 10 สามารถทำได้โดยการกระโดดเช่นนี้ อย่างไรก็ดี โปรแกรมที่ใช้การกระโดดมักยากต่อการเข้าใจและเหตุผล โดยเฉพาะเมื่อใช้การกระโดดอย่างสุ่มสี่สุ่มห้า ซึ่งผลลัพธ์มักถูกเรียกว่า spaghetti code ดังนั้นการใช้การกระโดดจึงถูกเลิกใช้เป็นวิธีแสดงอัลกอริทึม แม้ว่าจะยังใช้ในตัวแทนระดับต่ำของโค้ดที่รันบนฮาร์ดแวร์คอมพิวเตอร์ แทนที่จะใช้การกระโดด อัลกอริทึมจึงใช้ conditionals, loops และ recursion

เนื่องจากการกระโดดแบบชัดแจ้งเป็นโครงสร้างการควบคุมที่ถูกลดความนิยม เราจะเขียนอัลกอริทึม ToDo โดยไม่ใช้การกระโดดได้อย่างไร ในกรณีนี้ แทนที่จะใช้ปีเฉพาะเพื่อใส่ป้ายกำกับลำดับของการกระทำ เราสามารถใช้ชื่อเป้าหมาย (goals) ที่อัลกอริทึมตั้งใจจะบรรลุ เมื่ออัลกอริทึมถูกเรียกด้วยเป้าหมายเฉพาะ เราสามารถหา สมการสำหรับเป้าหมายนั้นจากสมการทั้งหมด นอกจากนี้ เมื่อการรันแบบ recursive เสร็จสิ้น เราจะกลับไปยังจุดที่เริ่มโดยอัตโนมัติ ในขณะที่ปีที่แน่นอนสำคัญสำหรับภาพยนตร์เพื่อสร้างบริบททางวัฒนธรรมต่าง ๆ แต่สำหรับการกำหนดลำดับขั้นตอนที่ถูกต้อง ปีเหล่านั้นไม่สำคัญ เพราะลำดับขึ้นอยู่กับการเรียงลำดับสัมพัทธ์ที่เคารพการพึ่งพาเชิงสาเหตุของการกระทำ ดังนั้นเราจึงสามารถแทนที่อัลกอริทึม ToDo ด้วยอัลกอริทึมใหม่ Goal นิยามดังนี้:

Goal(live now)	\= Goal(restore world); go camping
Goal(restore world)	\= retrieve sports alamanac; Goal(save Doc)
Goal(save Doc)	\= help Doc avoid Buford Tannen

การคำนวณสำหรับอัลกอริทึมนี้ดำเนินไปในลักษณะเดียวกับอัลกอริทึม ToDo เพียงแต่ไม่มีการระบุปีอย่างชัดเจน และการกลับสู่ปี 1985 เกิดขึ้นเป็นสองขั้นตอน

ทันเวลา (Just in Time)

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

อัลกอริทึมนี้ต้องแยกสองกรณี ครั้งแรก หากสำรับว่างเปล่า จะมีไพ่ 0 ใบ ประการที่สอง หากสำรับไม่ว่าง จำนวนไพ่สามารถหาได้โดยการบวก 1 ให้กับจำนวนไพ่ในสำรับที่เอาไพ่บนสุดออก หากเราแทนสำรับไพ่ด้วยโครงสร้างข้อมูลแบบ list อัลกอริทึมต้องแยกความแตกต่างระหว่าง list ว่างและ list ที่ไม่ว่าง ในกรณีหลัง จะบวก 1 ให้กับผลลัพธ์ของการประยุกต์อัลกอริทึมกับ tail ของ list (ซึ่งคือ list ที่ไม่มีสมาชิกตัวแรก) เนื่องจากการเรียกซ้ำใด ๆ กับ list ที่ไม่ว่างจะนำไปสู่การเพิ่ม 1 ด้วยตัวมันเอง อัลกอริทึมจะเพิ่มจำนวน 1 เท่ากับจำนวนองค์ประกอบใน list อัลกอริทึม Count สามารถอธิบายได้ด้วยสองสมการต่อไปนี้ที่จัดการกับกรณี list ว่างและ list ที่ไม่ว่าง:

Count( )	\= 0
Count(x_→_rest)	\= Count(rest) + 1

สองกรณีถูกแยกด้วยการแสดงรูปแบบอาร์กิวเมนต์ที่ต่างกันสำหรับ Count ในด้านซ้ายของสมการ ในสมการแรก ช่องว่างหมายความว่าสมการนี้ใช้กับ lists ว่างที่ไม่มีสมาชิก ในสมการที่สอง รูปแบบ x_→_rest แทน list ที่ไม่ว่าง โดยที่ x แทนสมาชิกตัวแรกและ rest แทน tail ของ list นิยามในกรณีนี้จะนับองค์ประกอบใน tail ของ list โดยใช้ Count(rest) แล้วบวก 1 ให้กับผลลัพธ์ วิธีการเลือกกรณีต่าง ๆ สำหรับอัลกอริทึมนี้เรียกว่า pattern matching Pattern matching มักจะสามารถแทนที่การใช้ conditionals ได้และนำไปสู่การแยกแยะกรณีต่าง ๆ ที่ชัดเจนสำหรับอัลกอริทึม นอกจากนี้ pattern matching ยังให้การเข้าถึงส่วนของโครงสร้างข้อมูลที่อัลกอริทึมทำงานอยู่โดยตรง ซึ่งบางครั้งทำให้นิยามสั้นลง ในกรณีนี้ x อ้างถึงสมาชิกตัวแรกของ list แต่ไม่ได้ถูกใช้ในนิยามด้านขวาของสมการ แต่เนื่องจาก rest เป็นชื่อตัวแปรสำหรับ tail ของ list มันจึงถูกนำไปใช้เป็นอาร์กิวเมนต์สำหรับการเรียกแบบ recursive ไปยัง Count อีกประโยชน์หนึ่งของ pattern matching คือมันแยกส่วนที่เป็น recursive ออกจากส่วนที่ไม่ใช่ recursive อย่างชัดเจน

สมการแบบ recursive สำหรับ Count อาจเข้าใจได้ดังสมมุติฐานต่อไปนี้: หากเราทราบจำนวนองค์ประกอบใน tail ของ list แล้ว จำนวนทั้งหมดสามารถหาจากการบวก 1 กับจำนวนนั้น สมมติว่ามีคนมานับจำนวนไพ่ในสำรับที่เอาไพ่บนสุดออกแล้วและฝากโน้ตไว้บน sticky note โดยเขียนตัวเลขไว้ ในกรณีนั้น จำนวนทั้งหมดสามารถหาได้โดยการบวก 1 กับตัวเลขในโน้ต

อย่างไรก็ตาม เนื่องจากข้อมูลนี้ไม่มีให้เรา เราจึงต้องคำนวณมันอย่าง—แบบ recursive—โดยการประยุกต์ Count กับ tail ของ list นั่นคือ rest และนี่คือการเชื่อมโยงกับการเดินทางข้ามเวลา พิจารณาเวลาที่เกิดขึ้นของขั้นตอนการคำนวณต่าง ๆ หากเราต้องการบวก 1 ตอนนี้ การคำนวณ Count(rest) ต้องเสร็จสิ้นแล้ว และดังนั้นต้องถูกเริ่มในอดีตในบางช่วงเวลา เช่นเดียวกัน หากเราต้องการคำนวณจำนวนทั้งหมดทันที เราอาจขอให้คนอื่นมานับจำนวนไพ่ในสำรับที่เอาไพ่บนสุดออกให้เราเมื่อสักครู่ก่อน เพื่อให้ผลลัพธ์นั้นพร้อมใช้ในปัจจุบัน ดังนั้นเราสามารถมองว่าการเรียกแบบ recursive ของอัลกอริทึมเป็นการเดินทางย้อนเวลาที่สร้างขั้นตอนการคำนวณที่เสร็จสิ้นในปัจจุบันเพื่อให้ขั้นตอนถัดไปทำได้ทันที

เพื่อดูตัวอย่างการคำนวณแบบ recursive ที่ชัดเจน ลองนับสิ่งที่ Marty นำไปกับเขาในปี 1885 ซึ่งได้แก่ บู๊ตคาวบอย (B), วิทยุสื่อสาร (W), และ hoverboard (H) เมื่อเราใช้ Count กับ list B→W→H เราต้องใช้สมการที่สอง เพราะ list ไม่ว่าง ในการประยุกต์นี้ เราจำเป็นต้องจับคู่รูปแบบ x_→_rest กับ list ซึ่งทำให้ x อ้างถึง B และ rest อ้างถึง W→H สมการที่กำหนดสำหรับ Count จากนั้นสั่งให้บวก 1 ให้กับการเรียกแบบ recursive ของ Count กับ rest

Count(B→W→H) = Count(W→H) + 1

เพื่อจะทำการบวกนี้ เราต้องการผลลัพธ์ของ Count(W→H) ซึ่งเรารู้ว่าเป็น 2 แต่การคำนวณที่สอดคล้องกับ Count ต้องถูกเริ่มก่อนหน้านี้ถ้าเราต้องการใช้ผลลัพธ์ทันที

เพื่อให้เข้าใจเวลาได้ชัดขึ้น สมมติว่าขั้นตอนการคำนวณพื้นฐาน เช่น การบวกตัวเลขสองตัว ใช้เวลาหน่วยเวลาเดียว เราจึงพูดได้ถึงระยะเวลาของการคำนวณเป็นหน่วยเวลา ถ้าเรากำหนดให้ปัจจุบันเป็นเวลา 0 ขั้นตอนพื้นฐานที่ทำตอนนี้จะเสร็จที่เวลา +1 เช่นกัน การคำนวณที่ใช้สองขั้นตอนและเสร็จตอนนี้จะต้องเริ่มที่เวลา −2

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

โชคดีที่เราไม่จำเป็นต้องรู้ขนาดของอินพุตเพื่อใช้การเดินทางย้อนเวลาอย่างมีประสิทธิภาพ ข้อสังเกตหลักคือเพียงเริ่มการคำนวณเชิง recursive หนึ่งหน่วยเวลาในอดีตก็เพียงพอ เพราะไม่ว่าอัลกอริทึมเชิง recursive จะใช้เวลานานเท่าไร เวลาเพิ่มเติมที่จำเป็นสำหรับการเรียกซ้ำเพิ่มเติมจะได้มาจากการส่งการเรียกซ้ำนั้นยิ่งกลับไปในอดีตมากขึ้น วิธีการทำงานนี้อธิบายในรูปที่ figure 12.1

ดังที่แสดง การรัน Count(B→W→H) ทำให้เกิดการคำนวณ Count(W→H) + 1 เมื่อการคำนวณแบบ recursive เสร็จสิ้น Count จะใช้เวลาเพียงก้าวเดียวในการบวก 1 กับผลลัพธ์ของการเรียกซ้ำ และเราจะได้ผลลัพธ์สุดท้าย 3 พร้อมใช้ที่เวลา +1 เพื่อให้ผลของการเรียกซ้ำพร้อมใช้ในเวลาที่กำหนด ก็เพียงพอที่จะเริ่มการคำนวณก่อนหน้านั้นหนึ่งหน่วยเวลา ตัวอย่างเช่น เพื่อให้ค่า Count(W→H) พร้อมใช้ในปัจจุบัน (เวลา 0) เราต้องส่งการคำนวณนั้นหนึ่งหน่วยเวลาไปในอดีต ดังที่แสดงในการรูป การคำนวณนี้ให้ผลเป็นนิพจน์ 1 + 1 ที่เวลา −1 ซึ่งจะประเมินค่าในก้าวเดียวเป็น 2 ที่เวลา 0 ซึ่งตรงกับเวลาที่ต้องการ แล้วทำได้อย่างไรที่ Count(W→H) จะให้ค่า 1 + 1 ทันที? นั่นทำได้โดยการส่งการเรียกซ้ำที่เกี่ยวข้อง Count(H) ย้อนกลับไปหนึ่งก้าวในอดีต คือไปที่เวลา −2 ซึ่งมันจะให้ผลเป็นนิพจน์ 0 + 1 ซึ่งก็ประเมินค่าในก้าวเดียวและทำให้ผล 1 พร้อมใช้ที่เวลา −1 ค่า 0 ในนิพจน์มาจากการเรียก Count( ) ที่ถูกส่งกลับไปที่เวลา −3 โดยรวมเราเห็นว่าโดยการเริ่มการคำนวณเชิง recursive ย้อนอดีตซ้ำ ๆ เราสามารถจบการคำนวณต้นทางได้เพียงหนึ่งหน่วยเวลาในอนาคต นี่เป็นจริงไม่ว่ารายการจะยาวเท่าไร รายการที่ยาวกว่าจะเพียงสร้างการเดินทางย้อนเวลามากขึ้นไปในอดีต

Figure 12.1 การนับจำนวนองค์ประกอบใน list แบบ recursive โดยการเดินทางย้อนอดีต การรันอัลกอริทึม Count บน list ที่ไม่ว่างจะกระตุ้นการคำนวณที่บวก 1 กับผลของการคำนวณ Count สำหรับ tail ของ list การรันการคำนวณของ tail หนึ่งก้าวในอดีตทำให้ผลพร้อมใช้ในปัจจุบัน และผลการบวกจะพร้อมใช้หนึ่งก้าวในอนาคต การรัน Count บน list ที่ไม่ว่างในอดีตนำไปสู่การรัน Count อีกครั้งที่ย้อนกลับไปไกลยิ่งขึ้น

โปรดทราบว่าอนาล็อกการเดินทางข้ามเวลาอาจทำให้ recursion ดูซับซ้อนกว่าที่เป็นจริง เมื่ออัลกอริทึมเชิง recursive ถูกรันโดยคอมพิวเตอร์ ไม่จำเป็นต้องมีเทคนิกด้านเวลาและการจัดตารางที่ซับซ้อน สิ่งนี้เห็นได้ชัดจาก binary search ใน chapter 4 และ quicksort กับ mergesort ใน chapter 6

โมเดลการเดินทางข้ามเวลาอธิบายรูปแบบของ recursion สองรูปแบบและความสัมพันธ์ระหว่างพวกมัน ในทางหนึ่ง อัลกอริทึมเช่น Goal หรือ Count ใช้ recursion ในการนิยามผ่านการอ้างอิงตัวเอง ผมเรียกรูปแบบนี้ว่า descriptive เพราะ recursion เกิดขึ้นในคำอธิบายของอัลกอริทึม ในทางกลับกัน เมื่ออัลกอริทึมเชิง recursive ถูกเรียกใช้งาน ลำดับของเหตุการณ์หรือการคำนวณที่เกิดขึ้นเป็นการแสดงตัวอย่างของนิยามเชิง recursive โดยใช้ค่าพารามิเตอร์ต่างกัน ผมเรียกรูปแบบนี้ว่า unfolded ดังที่ figure 12.1 แสดง การขยายซ้ำของการเรียกใช้อัลกอริทึมเชิง recursive แปลงนิยามเชิง descriptive ให้เป็นการคำนวณเชิง unfolded กล่าวอีกนัยหนึ่ง การรันนิยามเชิง descriptive (คืออัลกอริทึมเชิง recursive) ให้ผลเป็นการคำนวณเชิง unfolded ซึ่งสรุปได้ในสมการต่อไปนี้:

Execution(Descriptive Recursion) = Unfolded Recursion

ภาพของห้องที่มีทีวีแสดงภาพห้องนั้นเองเป็นตัวอย่างของ unfolded recursion โดยให้ความสัมพันธ์ข้างต้น จะมีคำถามว่านิยามเชิง descriptive ใดบ้างที่เมื่อถูกรันจะให้ผลเป็นภาพ unfolded นั้น คำตอบคือมี เช่น คำสั่งให้ใช้กล้องวิดีโอถ่ายภาพนิ่งของห้องแล้วป้อนภาพนั้นเข้าไปยังทีวีที่อยู่ในห้อง เมื่อปฏิบัติตามคำสั่งนั้นก็จะได้ภาพแบบ unfolded ที่เป็นตัวอย่าง

ใน Back to the Future นิยามเชิง descriptive ถูกจับในอัลกอริทึม ToDo และ Goal โดยเฉพาะเป้าหมายและแผนในการเปลี่ยนอดีตเป็นรูปแบบของนิยามเชิง descriptive และเมื่อแผนเหล่านั้นถูกปฏิบัติ เรื่องราวจะคลี่คลายเป็นเหตุการณ์ที่มักจะคล้ายคลึงกัน เช่น ฉาก déjà vu ร้านกาแฟ/โรงเต้น และฉากสเกตบอร์ด/hoverboard

ไม่ได้มีเพียงตัวละครสมมติในหนังเดินทางข้ามเวลาเท่านั้นที่วางแผนและตั้งเป้าจะเปลี่ยนอดีต บางครั้งพวกเราทุกคนก็มีนิยามเชิง descriptive ของเรื่องราวโดยถามว่า “จะเกิดอะไรขึ้นถ้าฉันทำอย่างนั้นต่างออกไป?” อย่างไรก็ดี ไม่เหมือนตัวละครในหนัง เราไม่สามารถปฏิบัติแผนเหล่านั้นได้จริง

การต่อสู้กับปริศนาโดยใช้ fixed points (Fighting Paradoxes with Fixed Points)

การเดินทางข้ามเวลาเป็นหัวข้อที่น่าสนใจและบันเทิงส่วนหนึ่งเพราะมันสามารถสร้างปริศนา สถานการณ์ที่เป็นไปไม่ได้ที่มีการขัดแย้งทางตรรกะ เช่น อย่างหนึ่งก็เป็นและไม่เป็นอีกอย่าง ตัวอย่างที่รู้จักกันดีคือ grandfather paradox ซึ่งหมายถึงนักเดินทางข้ามเวลาที่ย้อนกลับไปฆ่าปู่ของตน (ก่อนที่ปู่จะมีบุตรซึ่งจะเป็นพ่อหรือแม่ของนักเดินทาง) ซึ่งทำให้การมีอยู่ของนักเดินทางเองเป็นไปไม่ได้ รวมทั้งการเดินทางย้อนเวลาและการฆ่าปู่ ปรากฏการณ์ grandfather paradox ถูกใช้เป็นเหตุผลว่าการเดินทางย้อนอดีตเป็นไปไม่ได้ เพราะมันนำไปสู่สถานการณ์ทางตรรกะที่ขัดแย้งกับความเข้าใจของเราถึงสาเหตุ ใน Back to the Future II Doc Brown เตือนเกี่ยวกับผลที่อาจเกิดขึ้นหาก Jennifer พบกับตัวเธอเองในอนาคต:

การพบกันอาจสร้างปริศนาข้ามเวลา ผลที่ตามมาอาจก่อให้เกิดปฏิกิริยาลูกโซ่ที่จะคลี่คลายเนื้อผ้าของ continuum เวลาและพื้นที่ และทำลายจักรวาลทั้งจักรวาล! ถือว่าเป็นกรณีเลวร้ายที่สุด การทำลายอาจถูกจำกัดให้อยู่เพียงกาแลกซีของเราเท่านั้น

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

คำถามที่เทียบเท่าของ grandfather paradox มีอยู่ในโลกของการคำนวณหรือไม่? มี เช่น การรันอัลกอริทึมเชิง recursive ที่ไม่ยุติเลย (nonterminating) นั้นสามารถถือเป็นปริศนาได้ ในต่อไปนี้ผมจะอธิบายมุมมองนี้อย่างละเอียดโดยใช้แนวคิดของ fixed point.

เพื่อสร้างปริศนา ดูเหมือนว่าเราจำเป็นต้องหาการคำนวณเชิง recursive ที่กระตุ้นการย้อนอดีตและเปลี่ยนมันจนการคำนวณที่กระตุ้นนั้นหายไปหรือเป็นไปไม่ได้ การหยุดก่อนจริง ๆ ที่จะย้อนเวลา แนวที่ใกล้เคียงที่สุดที่อาจทำนั้นคืออัลกอริทึมที่ลบตัวเองหรือทำลายคอมพิวเตอร์ที่มันรัน ในสถานการณ์เช่นนั้น การรันอัลกอริทึมนั้นก็จะหยุดไป จึงไม่มีปริศนาจริง ๆ ที่ต้องแก้ในกรณีนั้น แต่ตัวอย่างนี้เป็นเพียงการดู unfolded recursion เท่านั้น มีหลายกรณีของ descriptive recursion ที่เป็นปริศนา จงจำการนิยามเชิง recursive ของ Count ที่ให้สมการว่าจำนวนองค์ประกอบใน list ได้มาจากการบวก 1 กับจำนวนของ tail ไม่มีปัญหาในนี้ แต่สมมติว่าเราเปลี่ยนนิยามเล็กน้อยโดยใช้ Count กับทั้ง list แทนที่จะเป็น tail:

Count(list) = Count(list) + 1

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

n = n + 1

อีกครั้ง นี่เป็นการขัดแย้งหรือปริศนา และสมการไม่มีคำตอบ ในแง่มุมของการเปรียบเทียบการเดินทางย้อนเวลา ความพยายามจะย้อนกลับไปคำนวณค่าสำหรับ n หรือ Count(list) จะไม่ยุติและจึงไม่สามารถถึงจุดที่เราจะบวก 1 ได้ กล่าวคือ ไม่มีวิธีที่การกระทำที่ต้องการในอดีตจะถูกดำเนินการให้สอดคล้องกับการกระทำในปัจจุบัน ซึ่งเท่ากับปริศนาว่าจำนวนองค์ประกอบใน list ควรมีค่าต่างกันสองค่าในเวลาเดียวกัน

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

Chapter 9 ได้หารือว่า ภาษาโปรแกรมมี semantics และ semantics ของอัลกอริทึมที่เขียนในภาษาหนึ่งหมายถึงการคำนวณที่เกิดขึ้นเมื่อรันอัลกอริทึมนั้น จากมุมมองนี้ ความหมายของอัลกอริทึมที่ขัดแย้งและนำไปสู่ปริศนาเป็น undefined กล่าวคือ ไม่มีการคำนวณที่จะทำในสิ่งที่อัลกอริทึมร้องขอ เราจะบอกได้อย่างไรว่าอัลกอริทึมเชิง recursive นั้นขัดแย้งและนำไปสู่ปริศนา?

ตัวอย่างของการนิยามตัวเลขเชิง recursive สามารถช่วยทำให้ปัญหาชัดเจน พิจารณาสมการต่อไปนี้ซึ่งบอกว่าสิ่งที่นิยามคือจำนวนที่เท่ากับกำลังสองของมันเอง:

n = n × n

นี่ไม่ใช่การขัดแย้ง มีจำนวนเต็มสองจำนวนที่ทำให้สมการเป็นจริง ได้แก่ 1 และ 0 และนี่คือกุญแจในการเข้าใจนิยามเชิง recursive จำนวนที่นิยามคือคำตอบของสมการ นั่นคือ จำนวนที่เมื่อแทนค่าให้ตัวแปร n จะทำให้สมการเป็นจริง ไม่ใช่การขัดแย้ง ในกรณีของสมการนี้ เราได้ 1 = 1 × 1 ซึ่งเป็นจริง ดังนั้น 1 เป็นคำตอบของสมการนั้น ในทางกลับกัน สมการ n = n + 1 ไม่มีคำตอบ ในทำนองเดียวกัน สมการ Count(list) = Count(list) + 1 ก็ไม่มีคำตอบเช่นกัน แต่สมการดั้งเดิมมีคำตอบ ในกรณีนั้นมันคือการคำนวณที่คำนวณจำนวนองค์ประกอบใน list

สมการที่มีตัวแปรเดียวกันทั้งสองข้างสามารถมองว่าเกิดจากการแปลง (transformation) ตัวอย่างเช่น สมการ n = n + 1 บอกว่า n ถูกกำหนดโดยการบวก 1 ให้กับมันเอง หรือ n = n × n บอกว่า n ถูกกำหนดโดยการคูณมันเองกับตัวมันเอง ค่าจำนวนใด ๆ ที่ไม่เปลี่ยนแปลงโดยการแปลงนี้เรียกว่า fixed point ของการแปลงนั้น ตามชื่อที่สื่อถึง ค่านั้นจะไม่เปลี่ยนและถูกตรึงไว้

ตัวอย่างของ fixed points ที่ทำให้คำว่า "จุด" เหมาะสมยิ่งขึ้นมาจากการแปลงเชิงเรขาคณิต ลองพิจารณาการหมุนภาพรอบศูนย์กลาง ทุกจุดจะเปลี่ยนตำแหน่งยกเว้นศูนย์กลางซึ่งยังคงอยู่ที่เดิม ศูนย์กลางคือ fixed point ของการหมุน ในความจริง ศูนย์กลางเป็น fixed point เดียวของการหมุน หรือพิจารณาการสะท้อนภาพตามเส้นทแยงมุม ในกรณีนี้ จุดทั้งหมดบนทแยงมุมเป็น fixed points ของการสะท้อน สุดท้าย การเลื่อนภาพไปทางซ้ายไม่มี fixed point เพราะทุกจุดถูกกระทบ สำหรับตัวอย่างเชิงตัวเลข การแปลง "บวก 1" จะไม่มี fixed point ในขณะที่การแปลง "คูณตัวเอง" จะมีสอง fixed points คือ 1 และ 0

การแปลงที่สอดคล้องกับสมการที่นิยาม Count คืออะไร? ก่อนอื่น เราสังเกตว่านิยามที่เปลี่ยนไป Count(list) = Count(list) + 1 ใกล้เคียงกับนิยาม n = n + 1 เพียงแต่ว่ามันมีพารามิเตอร์ นิยามนี้สอดคล้องกับการแปลงที่บอกว่า การประยุกต์ของ Count กับ list ถูกกำหนดโดยการบวก 1 ให้กับการประยุกต์นั้น การแปลงนี้ เหมือนกับการแปลงสำหรับสมการของ n ไม่มี fixed point ในทางตรงกันข้าม การแปลงสำหรับนิยามเดิม Count(x_→_rest) = Count(rest) + 1 บอกว่า การใช้ Count กับ list ถูกกำหนดโดยการลบสมาชิกตัวแรกของ list ในการประยุกต์นั้นแล้วบวก 1 การแปลงนี้ (รวมกับสมการที่กำหนดกรณีสำหรับ list ว่าง) มี fixed point ซึ่งกลายเป็นฟังก์ชันที่นับจำนวนองค์ประกอบใน list

ความหมายของสมการเชิง recursive คือ fixed point ของการแปลงพื้นฐาน—นั่นคือ ถ้ามี fixed point อยู่ เมื่อสมการเชิง recursive อธิบายอัลกอริทึม fixed point จะบรรยายการคำนวณที่เสถียรภายใต้การแปลงที่ทำให้มันสามารถประยุกต์ได้กับกรณีจำนวนมาก การแปลงมักจะปรับอาร์กิวเมนต์ของอัลกอริทึม และอาจเปลี่ยนแปลงผลของการเรียกซ้ำ ในกรณีของ Count อาร์กิวเมนต์ list จะถูกลบสมาชิกตัวแรกออก และผลลัพธ์จะเพิ่มขึ้นหนึ่ง ในกรณีของ Goal สมการเชิง recursive จะรัน Goal กับเป้าหมายต่าง ๆ และเพิ่มกิจกรรมอื่น ๆ ที่เกี่ยวข้องกับแต่ละกรณี

จากมุมมองการเดินทางย้อนเวลา fixed point ของอัลกอริทึมเชิง recursive บรรยายการคำนวณที่ผลกระทบในอดีตสอดคล้องกับผลกระทบในปัจจุบัน นี่คือเหตุผลที่ fixed points เกี่ยวข้องกับ recursion อัลกอริทึมเชิง recursive เช่นนักเดินทางข้ามเวลาจะต้องทำงานอย่างถูกต้องและหลีกเลี่ยงปริศนา หากอัลกอริทึมเชิง recursive มี fixed point มันหมายถึงการคำนวณที่มีความหมาย มิฉะนั้นมันก็เป็นปริศนา อย่างไรก็ดี ต่างจากปริศนาการเดินทางข้ามเวลาที่อาจทำลายจักรวาล มันเพียงแค่ไม่คำนวณสิ่งที่คุณต้องการ การเข้าใจความหมายของอัลกอริทึมเชิง recursive ในฐานะ fixed point ไม่ใช่เรื่องง่าย Chapter 13 แสดงวิธีอีกทางหนึ่งในการทำความเข้าใจกับนิยามเชิง recursive

จะใช้ loop หรือไม่ (To Loop or Not to Loop)

Recursion เป็นโครงสร้างการควบคุมที่เทียบเท่ากับ loops กล่าวคือ loop ใด ๆ ในอัลกอริทึมสามารถแทนที่ด้วย recursion และกลับกัน ในบางตัวอย่างทางเลือกหนึ่งอาจรู้สึกเป็นธรรมชาติมากกว่าอีกด้านหนึ่ง แต่นิสัยนี้มักเกิดจากการคุ้นเคยกับโครงสร้างการควบคุมใด ๆ มาก่อน เช่น จะมองอัลกอริทึมตามรอยก้อนหินของ Hansel และ Gretel ว่าเป็น loop อย่างไรได้

หาเพชรที่ไม่เคยถูกเยี่ยมมาก่อน แล้วเดินไปหามันจนกว่าคุณจะถึงบ้าน

มันชัดเจนว่าเป็นตัวอย่างของ repeat loop ในขณะที่นี่เป็นคำอธิบายที่ชัดเจนและเรียบง่ายของอัลกอริทึม เวอร์ชันเชิง recursive ที่เทียบเท่า FindHomeFrom ยาวขึ้นเพียงเล็กน้อย:

FindHomeFrom(home) = do nothing

FindHomeFrom(forest) = FindHomeFrom(next unvisited pebble)

เช่นเดียวกับอัลกอริทึมเชิง recursive อื่น ๆ ที่นำเสนอที่นี่ FindHomeFrom ถูกกำหนดด้วยสมการหลายสมการที่แยกกรณีต่าง ๆ ที่ต้องพิจารณาด้วยพารามิเตอร์ ในกรณีนี้ พารามิเตอร์แทนตำแหน่งที่อัลกอริทึมค้นหาทางกลับบ้าน และสองกรณีคือว่าตำแหน่งปัจจุบันของ Hansel และ Gretel เป็นบ้านแล้วหรือยังอยู่ในป่า

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

การนิยามเชิง recursive แสดงให้เห็นว่า loop สามารถแสดงด้วย recursion ได้อย่างไร ประการแรก ผลลัพธ์สองแบบของเงื่อนไขการยุติ (ถึงบ้านหรือยังอยู่ในป่า) ถูกแสดงเป็นพารามิเตอร์ของสมการ ประการที่สอง เนื้อหาของ loop กลายเป็นส่วนหนึ่งของสมการที่พารามิเตอร์แทนกรณีที่ไม่ยุติ (ในที่นี้คือ ตำแหน่งอยู่ในป่า) ประการที่สาม การดำเนินการต่อของ loop ถูกแสดงเป็นการเรียกแบบ recursive ของอัลกอริทึมโดยใช้อาร์กิวเมนต์ที่เปลี่ยนแปลงอย่างเหมาะสม (ในที่นี้คือตำแหน่งของก้อนหินที่ยังไม่ถูกเยี่ยม)

ผมได้แสดงเวอร์ชันเชิง recursive ของ Groundhog Day loop ใน chapter 10 โดยใช้ conditional โดยการใช้สมการและ pattern matching เราสามารถแสดง Groundhog Day loop ได้ดังนี้:

GroundhogDay(true) = do nothing

GroundhogDay(false) = experience the day; GroundhogDay(good person?)

เมื่อเทียบกับ loop repeat experience the day until good person คำอธิบายนี้ดูซับซ้อนกว่าเล็กน้อย แต่มันจะผิดที่จะสรุปว่า loops มักจะเขียนโปรแกรมได้ง่ายกว่า recursion เสมอ Recursion เหมาะเป็นพิเศษสำหรับปัญหาที่สามารถแบ่งย่อยเป็นปัญหาย่อย (ดู divide-and-conquer ใน chapter 6) อัลกอริทึมเชิง recursive สำหรับปัญหาเหล่านี้มักจะเรียบง่ายและชัดเจนกว่ารูปแบบที่ใช้ loop การฝึกปฏิบัติก็คือ ลองเขียนอัลกอริทึมเช่น quicksort โดยไม่ใช้ recursion เพื่อเห็นคุณค่าของสิ่งนี้

หลายรูปแบบของ recursion (The Many Faces of Recursion)

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

• Execution: unfolded vs. descriptive
• Termination: bounded vs. unbounded
• Reach: direct vs. indirect

ผมได้กล่าวถึงความแตกต่างระหว่าง unfolded และ descriptive recursion แล้วและวิธีที่พวกมันเชื่อมโยงกันผ่านการคำนวณ จำได้ไหมว่าการรันนิยามเชิง descriptive จะให้ผลเป็น unfolded recursion ซึ่งช่วยในการทำความเข้าใจสถานการณ์เชิง recursive ในด้านหนึ่ง เมื่อเจอ unfolded recursion เราสามารถพยายามคิดถึงนิยามเชิง descriptive ที่เมื่อรันจะให้ผลเป็น unfolded recursion นั้น นิยามเชิง descriptive มักให้ลักษณะกะทัดรัดของสถานการณ์ โดยเฉพาะเมื่อ recursion เป็นแบบไม่จำกัด ในอีกด้านหนึ่ง เมื่อมีนิยามเชิง descriptive เรามักได้ประโยชน์จากการรันนิยามเพื่อดูเวอร์ชัน unfolded โดยเฉพาะเมื่อ recursion มีรูปแบบซับซ้อน เช่น เมื่อต้องมีการเกิด recursion หลายครั้ง สำหรับตัวอย่างภาพห้องกับทีวี หากเพิ่มกล้องตัวที่สองและทีวีตัวที่สองเพื่อให้กล้องทั้งสองสามารถบันทึกภาพซึ่งรวมทั้งภาพทีวีทั้งสองได้ ผลลัพธ์จะเป็นอย่างไร การเห็นว่านิยามเชิง descriptive ผลิต unfolded recursion อย่างไรช่วยให้เข้าใจ recursion ได้ดีขึ้น

การเรียกซ้ำแบบ bounded คือการที่มันยุติ สำหรับ unfolded recursion เท่านั้นจึงสมเหตุสมผลที่จะจำแนกระหว่าง bounded และ unbounded อย่างไรก็ตาม เราสามารถถามว่าข้อกำหนดสำหรับนิยามเชิง descriptive ที่จะทำให้ recursion ยุติมีอะไรบ้าง หนึ่งในเงื่อนไขคือคำอธิบายของ recursion ต้องมีบางส่วนที่ไม่เรียก recursion ตัวเอง เช่น นิยามสำหรับ Goal(save Doc) หรือ Count() สมการที่เป็นเช่นนี้เรียกว่า base cases แม้ base case จะเป็นสิ่งจำเป็นเพื่อสิ้นสุด recursion แต่มันไม่รับประกันการยุติเพราะกรณี recursion อาจทำให้ไม่ไปถึง base case โปรดจำการนิยาม Count(list) = Count(list) + 1 ซึ่งจะไม่มีการยุติเมื่อใช้กับ list ที่ไม่ว่าง แม้ว่าจะมี base case สำหรับ list ว่าง

การเรียกซ้ำแบบไม่จำกัดจะมีประโยชน์ไหม? ดูเหมือนว่าการคำนวณเชิง recursive ที่ไม่ยุติจะไม่สามารถให้ผลลัพธ์ได้และจึงไม่มีความหมาย แต่ถ้าเรามองเป็นส่วนประกอบของการคำนวณอื่น ๆ การเรียกซ้ำไม่จำกัดอาจมีประโยชน์ สมมติว่าการคำนวณสร้างสตรีมไม่สิ้นสุดของตัวเลขสุ่ม สตรีมดังกล่าวอาจมีประโยชน์สำหรับการจำลองตราบเท่าที่มีการบริโภคเพียงส่วนจำกัดของสตรีมที่ไม่สิ้นสุดนั้น และการคำนวณก็จะทำงานได้ดีและเพิกเฉยต่อส่วนที่ไม่สิ้นสุด อีกตัวอย่างคือการนิยามรายการอนันต์ของค่าหนึ่ง (Ones) ดังนี้:

Ones = 1→Ones

การรันนิยามนี้จะนำไปสู่ลำดับอนันต์ของ 1 ดังนี้:

1→1→1→1→1→1→ …

เหมือนกับภาพห้องกับทีวี รายการนี้มีตัวมันเองเป็นส่วน หน้าที่แสดงผ่านสมการและผ่าน unfolded list รายการอนันต์ของ 1 เริ่มด้วย 1 แล้วตามด้วยรายการของ 1 ซึ่งก็คืออนันต์

มุมมองนี้ของการบรรจุตัวเองยังช่วยอธิบาย self-similarity ว่าเป็นผลมาจาก recursion หากเราเขียนรายการที่ Ones คำนวณเป็นบรรทัดหนึ่ง และรายการที่ 1→Ones บรรทัดถัดไป เราจะเห็นสองรายการที่เหมือนกันอย่างสมบูรณ์ เนื่องจากทั้งสองเป็นอนันต์ รายการบนบรรทัดที่สองจะไม่มีองค์ประกอบเพิ่มขึ้นมา

การเรียกซ้ำที่ไม่สิ้นสุดยังพบได้ในดนตรี เช่น เพลงที่ร้องไม่รู้จบ (“99 bottles of beer on the wall”) หรือภาพวาดของ M. C. Escher เช่น “Drawing Hands” และ “Print Gallery.” งาน “Drawing Hands” แสดงมือหนึ่งวาดมือที่สอง ซึ่งทำหน้าที่วาดมือแรก ไม่มี base case และ recursion ไม่สิ้นสุด ในทำนองเดียวกัน “Print Gallery” แสดงการวนไม่ยุติ มันเป็นภาพของเมืองที่มีแกลเลอรีที่ชายคนหนึ่งมองภาพของเมืองเดียวกันนั้น ซึ่งรวมภาพเขาในแกลเลอรีที่มองภาพ

ภาพวาดสองชิ้นของ Escher แสดงความแตกต่างระหว่าง recursion แบบ direct และ indirect ใน “Drawing Hands” recursion เป็นแบบ indirect เพราะแทนที่จะวาดตัวเอง แต่ละมือวาดมือที่แตกต่างกัน — มือที่วาดมัน ในทางตรงกันข้าม ภาพ “Print Gallery” มีตัวมันเองโดยตรง เพราะมันแสดงเมืองที่มีแกลเลอรีซึ่งผู้ชายคนนั้นมองภาพ ตัวอย่าง “Drawing Hands” ยังแสดงให้เห็นว่า recursion แบบ indirect ไม่ได้รับประกันการยุติ สถานการณ์นี้คล้ายกับ base cases: พวกมันจำเป็นสำหรับการยุติแต่ไม่รับประกันการยุติ

ตัวอย่างที่นิยมของ recursion แบบ indirect คือการนิยามอัลกอริทึม Even และ Odd เพื่อกำหนดว่าจำนวนเป็นคู่หรือคี่ นิยามของ Even กล่าวว่า 0 เป็นจำนวนคู่ และตัวเลขอื่นใดเป็นจำนวนคู่ถ้าตัวเลขก่อนหน้าของมันเป็นคี่ ในสมการที่สอง นิยามของ Even อ้างถึงอัลกอริทึม Odd นิยามของ Odd กล่าวว่า 0 ไม่ใช่จำนวนคี่ และตัวเลขอื่นใดเป็นคี่ถ้าตัวเลขก่อนหน้าของมันเป็นคู่ ในสมการที่สอง นิยามของ Odd อ้างถึงอัลกอริทึม Even ดังนั้น Even อ้างอิง recursive ถึงตัวมันเองโดยทางอ้อมผ่านการอ้างถึง Odd (และในทางกลับกัน) สามารถเห็นได้เมื่อประเมินตัวอย่างง่าย ๆ:

Even(2) = Odd(2 − 1) = Odd(1) = Even(1 − 1) = Even(0) = true

เราจะเห็นว่าการเรียก Even(2) ถูกลดเหลือการเรียก Even(0) แต่เป็นไปทางอ้อมผ่าน Odd นิยามของ Even และ Odd คล้ายกับ “Drawing Hands” ที่แต่ละนิยามกำหนดอีกนิยามหนึ่ง ความแตกต่างสำคัญคือ recursion ในอัลกอริทึมมีการจำกัด (การคำนวณใด ๆ จะยุติด้วยหนึ่งใน base cases), ในขณะที่ recursion ในภาพวาดเป็นแบบไม่จำกัด

Recursion [n], ดู Recursion.

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