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

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

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

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

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

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

It’s about Time (เรื่องของเวลา)

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

ดร.บราวน์: เห็นได้ชัดว่าสายเวลาถูกรบกวน ทำให้เกิดลำดับเหตุการณ์ใหม่ที่นำไปสู่ความเป็นจริงทางเลือกนี้

มาร์ตี้: พูดภาษาไทยสิครับ ดร.บราวน์!

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

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

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

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

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

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

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

ToDo (1985) = ToDo (1955); go camping

ToDo (1955) = retrieve sports alamanac ; ToDo (1885); return to 1985

ToDo (1885) = help Doc avoid Buford Tannen ; return to 1985

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

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

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

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

ฉันมันประมาทได้ขนาดนี้เลยเหรอ? 1.21 กิกะวัตต์! ทอม [โทมัส เอดิสัน], ฉันจะสร้างพลังงานขนาดนั้นได้ยังไง? มันเป็นไปไม่ได้ มันเป็นไปไม่ได้!

No Matter When (ไม่ว่าช่วงเวลาไหนก็ตาม)

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

เนื่องจากการกระโดดอย่างชัดเจนเป็นโครงสร้างควบคุมที่เลิกใช้แล้ว เราจะแสดง อัลกอริทึม ToDo โดยไม่ใช้มันได้อย่างไร? ในกรณีนี้ แทนที่จะใช้ปีที่เฉพาะเจาะจงในการติดป้ายกำกับลำดับของการกระทำ เราสามารถใช้ชื่อสำหรับเป้าหมายที่อัลกอริทึมตั้งใจจะบรรลุ เมื่ออัลกอริทึมถูกเรียกด้วยเป้าหมายหนึ่ง เราสามารถหาสมการสำหรับเป้าหมายนั้นจากบรรดาสมการต่างๆ ยิ่งไปกว่านั้น เมื่อการดำเนินการแบบเรียกซ้ำเสร็จสิ้น เราจะกลับไปยังจุดที่เริ่มต้นโดยอัตโนมัติ แม้ว่าปีที่แน่นอนจะสำคัญมากสำหรับภาพยนตร์ เพื่อสร้างบริบททางวัฒนธรรมที่แตกต่างกัน แต่มันไม่สำคัญสำหรับการสร้างลำดับขั้นตอนที่ถูกต้อง ซึ่ง ขึ้นอยู่กับการจัดลำดับสัมพัทธ์ที่เคารพการพึ่งพาเชิงสาเหตุของการกระทำเท่านั้น ดังนั้นเราสามารถแทนที่อัลกอริทึม 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 (ทันเวลา)

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

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

Count ( )	= 0
Count ( x → rest )	= Count ( rest ) + 1

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

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

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

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

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

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

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

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

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

ดังที่แสดง การดำเนินการของ Count (B→W→H) สร้างการคำนวณของ Count (W→H) + 1 เมื่อการคำนวณแบบเรียกซ้ำเสร็จสมบูรณ์ 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 โดยรวมแล้วเราจะเห็นว่าการเริ่มต้นการคำนวณแบบเรียกซ้ำซ้ำๆ ใน อดีต ทำให้เราสามารถเสร็จสิ้นการคำนวณเดิมได้ในอนาคตเพียง 1 หน่วยเวลาเท่านั้น สิ่งนี้เป็นจริงไม่ว่าลิสต์จะยาวแค่ไหนก็ตาม ลิสต์ที่ยาวกว่าก็แค่สร้างการเดินทางข้ามเวลาที่ไกลกลับไปในอดีตมากขึ้นเท่านั้น

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

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

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

Execution(Descriptive Recursion) = Unfolded Recursion

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

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

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

Fighting Paradoxes with Fixed Points (การต่อสู้กับความขัดแย้งด้วยจุดตรึง)

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

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

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

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

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

Count ( list ) = Count ( list ) + 1

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

n = n + 1

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

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

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

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

n = n × n

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

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

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

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

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

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

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

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

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

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

FindHomeFrom ( home ) = do nothing

FindHomeFrom ( forest ) = FindHomeFrom ( next unvisited pebble )

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

อัลกอริทึมแบบเรียกซ้ำอาจมีความแม่นยำมากกว่าเวอร์ชันลูปเล็กน้อย เนื่องจากมันสิ้นสุดในกรณีที่ พ่อของฮันเซลกับเกรเทลพาพวกเขาไปที่สนามหลังบ้าน ในกรณีนั้นฮันเซลจะไม่หย่อนก้อนกรวดใดๆ เพราะพวกเขาไม่เคย ออกจากบ้าน อย่างไรก็ตาม อัลกอริทึมแบบลูปสั่งให้พวกเขาหาก้อนกรวด ซึ่งจะนำไปสู่การคำนวณที่ไม่สิ้นสุด นี่ไม่ใช่ปัญหาของลูปโดยตัวมันเอง แต่เป็นผลมาจากการใช้รีพีตลูปในการอธิบายอัลกอริทึม โดยที่ไวล์ลูป "While you are not home, find a pebble not visited before, and go toward it" (ตราบใดที่คุณยังไม่ถึงบ้าน ให้หาก้อนกรวดที่ยังไม่เคยไปแล้วเดินไปหามัน) จะเหมาะสมกว่าเพราะมันทดสอบเงื่อนไขการสิ้นสุดก่อนที่จะดำเนินการเนื้อหาของลูป

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

ฉันได้แสดงเวอร์ชันแบบเรียกซ้ำของลูป Groundhog Day ใน บทที่ 10 โดยใช้เงื่อนไข การใช้สมการและการจับคู่รูปแบบ เราสามารถแสดงลูป Groundhog Day ได้ด้วยวิธีการดังต่อไปนี้:

GroundhogDay ( true ) = do nothing

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

เมื่อเปรียบเทียบกับลูป repeat   experience the day   until   good person สิ่งนี้ดูเหมือนจะซับซ้อนกว่า แต่คงไม่ถูกต้องที่จะสรุปว่าลูปนั้นง่ายต่อการเขียนโปรแกรม มากกว่าการเรียกซ้ำเสมอไป การเรียกซ้ำเหมาะสมเป็นพิเศษสำหรับปัญหาที่สามารถย่อยสลายเป็นปัญหาย่อยได้ (ดู อัลกอริทึมแบ่งแยกและเอาชนะใน บทที่ 6 ) อัลกอริทึมแบบเรียกซ้ำสำหรับปัญหาเหล่านั้นมักจะเรียบง่ายและชัดเจนกว่าเวอร์ชันที่ใช้ลูป เป็นแบบฝึกหัดที่มีประโยชน์ในการลองใช้อัลกอริทึม เช่น ควิกซอร์ต โดยไม่ใช้ การเรียกซ้ำเพื่อให้เห็นจุดนี้

The Many Faces of Recursion (ใบหน้าหลายด้านของการเรียกซ้ำ)

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

• การดำเนินการ: แบบคลี่คลาย vs. เชิงพรรณนา
• การสิ้นสุด: แบบมีขอบเขต vs. ไม่มีขอบเขต
• การเข้าถึง: โดยตรง vs. โดยอ้อม

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

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

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

Ones = 1→ Ones

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

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

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

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

การเรียกซ้ำแบบไม่มีขอบเขตยังพบได้ในดนตรี เช่น ในเพลงที่ไม่มีวันจบ ("99 bottles of beer on the wall" และอื่นๆ) หรือในภาพวาดของเอ็ม. ซี. เอสเชอร์ เช่น "Drawing Hands" และ "Print Gallery" 6 ผลงาน "Drawing Hands" แสดงให้เห็นมือข้างหนึ่งกำลังวาดมืออีกข้างหนึ่ง ซึ่งในทางกลับกันก็วาดมือข้างแรก ไม่มีกรณีพื้นฐาน และการเรียกซ้ำก็ไม่สิ้นสุด ในทำนองเดียวกัน "Print Gallery" แสดงการเรียกซ้ำที่ไม่สิ้นสุด เป็นภาพของเมืองที่มีแกลเลอรีซึ่งมีชายคนหนึ่งกำลังดูรูปภาพของเมืองเดียวกันนั้นที่รวมถึงตัวเขา ในแกลเลอรีที่กำลังดูรูปภาพนั้น

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

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

Even (0) = true	Odd (0) = false
Even ( n ) = Odd ( n − 1)	Odd ( n ) = Even ( n − 1)

ดังนั้น Even อ้างอิงกลับไปยังตัวเองโดยอ้อมผ่านการอ้างอิงถึง Odd (และในทางกลับกัน) สิ่งนี้สามารถเห็นได้เมื่อประเมินตัวอย่างง่ายๆ:

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

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

อีกตัวอย่างหนึ่งของการเรียกซ้ำโดยตรงคือนิยามแบบพจนานุกรมต่อไปนี้ของการเรียกซ้ำ: 8

Recursion [n], see Recursion.

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