บทที่ 12 มุ่งอธิบายว่า recursion คืออะไร รูปแบบต่างๆ ของมัน และความสัมพันธ์ระหว่าง recursion กับ loops. การรัน algorithms ToDo และ Count แสดงให้เห็นว่า descriptive recursion เมื่อถูกดำเนินการจะกลายเป็น unfolded recursion ซึ่งเผยให้เห็นว่าการอ้างอิงตัวเอง (self-reference) และความคล้ายคลึงของโครงสร้าง (self-similarity) เป็นการคำนวณ อย่างไรก็ตาม เรายังไม่ได้ลงรายละเอียดว่าการคำนวณแบบ recursive ทำงานอย่างไร

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

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

ประการที่สอง แนวคิดของ interpreter ให้มุมมองอีกแบบหนึ่งในการอธิบายอัลกอริทึมแบบ recursive Interpreter เป็นชนิดพิเศษของคอมพิวเตอร์ที่รันอัลกอริทึมโดยใช้ stack data type (ดู chapter 4) เพื่อเก็บการเรียกซ้ำ (ทั้ง recursive และ nonrecursive) และสำเนาของอาร์กิวเมนต์ที่เกิดขึ้นจากการรันแบบ recursive การทำงานของ interpreter ซับซ้อนกว่า substitution แต่ก็ให้มุมมองที่ต่างออกไป นอกจากนี้ interpreter ยังสามารถสร้าง traces ของการคำนวณที่เรียบง่ายกว่าร่องรอยที่ได้จาก substitution เพราะมันเก็บแต่ data และไม่มี instructions นอกเหนือจากการอธิบายว่าการทำงานของ recursion เป็นอย่างไร ทั้งสองโมเดลนี้ช่วยอธิบายอีกมุมหนึ่งของ recursion คือความแตกต่างระหว่าง linear และ nonlinear recursion

Rewriting History (การเขียนประวัติศาสตร์ใหม่)

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

เมื่ออัลกอริทึมถูกเรียกใช้งาน การคำนวณจะทำงานบนค่าป้อนเข้าที่ถูก substituted ให้กับพารามิเตอร์ อัลกอริทึม getting-up ใน chapter 2 ประกอบด้วยคำสั่ง “Wake up at wake-up-time._” เพื่อรันอัลกอริทึมนั้น ต้องใส่ค่าตัวอย่างเช่นเวลา 6:30 a.m. (เช่น โดยการตั้งนาฬิกาปลุก) ดังนั้นคำสั่งจะกลายเป็น “Wake up at 6:30 a.m.” ซึ่งได้มาจากการแทนค่า 6:30 a.m. ให้พารามิเตอร์ _wake-up-time ในอัลกอริทึม

กลไกการแทนค่าสามารถใช้ได้กับอัลกอริทึมและพารามิเตอร์ทุกชนิด: ถ้วยน้ำสำหรับทำกาแฟ ก้อนกรวดสำหรับหาทาง สภาพอากาศสำหรับรายงานสภาพอากาศ เป็นต้น แน่นอนว่าการแทนค่าพารามิเตอร์ก็ใช้กับอัลกอริทึมแบบ recursive ด้วย ตัวอย่างเช่น quicksort และ mergesort ต้องใช้ list ที่จะถูกเรียงเป็น input; binary search มีพารามิเตอร์สองตัวคือ item ที่ต้องการหาและโครงสร้างข้อมูล (tree หรือ array) สำหรับการค้นหา; และอัลกอริทึม Count (ดู chapter 12) รับ list ที่จะถูกนับเป็น input

นอกจากนี้ ในการรันอัลกอริทึมแบบ recursive ยังมีการแทนค่าอีกรูปแบบหนึ่ง คือการแทนนิยามของอัลกอริทึมมาแทนชื่อของมันเอง ตัวอย่างเช่น ในการสาธิตว่า Count คำนวณจำนวนของสิ่งของที่ Marty เอาไปในการเดินทางไปปี 1885 ได้อย่างไร ลองมาดูสมการที่นิยามว่าอัลกอริทึม Count ทำอะไรสำหรับรายการที่ไม่ว่างอีกครั้ง:

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

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

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

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

การอธิบายนี้จะชัดเจนยิ่งขึ้นหากเราใช้สัญกรณ์สำหรับการอนุพันธ์ที่ถูกกล่าวถึงครั้งแรกใน chapter 8 ตามที่คุณอาจจำได้ ลูกศรถูกใช้เพื่อแสดงว่าตัวสัญลักษณ์ nonterminal ถูกขยายด้วยฝั่งขวาที่นิยามไว้ ลำดับของการขยายเช่นนี้สามารถใช้อนุมานสตริงหรือ syntax tree ตามกฎไวยากรณ์ของภาษาได้ เราสามารถมองสมการนิยามของอัลกอริทึมแบบ recursive ในแนวเดียวกันว่าเป็นกฎสำหรับการอนุมานการคำนวณ โดยใช้สัญกรณ์ลูกศร เราสามารถเขียนสมการก่อนหน้านี้ใหม่ได้ดังนี้:

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

ขั้นตอนสุดท้ายนี้แสดงให้เห็นว่าการแทนค่าส่วนใหญ่เกิดขึ้นภายในบริบทที่ไม่ได้รับผลกระทบจากการแทนค่า กล่าวคือ การแทนค่าแทนที่ส่วนหนึ่งของนิพจน์ที่ใหญ่กว่าและเปลี่ยนเฉพาะส่วนท้องถิ่น เปรียบเหมือนการเปลี่ยนหลอดไฟเก่าออกแล้วใส่หลอดไฟใหม่ โดยยังคงโคมไฟและส่วนอื่นของสภาพแวดล้อมไว้เหมือนเดิม ในตัวอย่างนี้ การแทน Count(H) + 1 มาแทน Count(W→H) เกิดขึ้นในบริบทของ “+ 1” เราจำเป็นต้องทำการแทนค่าอีกสองขั้นตอนเพื่อขยายให้ครบและกำจัดการเรียก Count ทั้งหมด:

Figure 13.1 นิยามภาพแบบ recursive — ให้ชื่อกับภาพที่ภายในภาพมีการอ้างอิงถึงชื่อตัวเอง ความหมายของนิยามแบบอ้างอิงตนเองสามารถได้จากการแทนชื่อด้วยภาพขนาดย่อซ้ำๆ ซึ่งสร้างการขยายแบบ unfolded recursion ทีละขั้นตอน

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

เราสามารถใช้กลยุทธ์เดียวกันนี้กับอัลกอริทึม ToDo และ Goal โดยใช้ substitution เพื่อติดตามการรันของอัลกอริทึมเดินทางข้ามเวลาแบบ recursive ซึ่งจะให้ลำดับของการกระทำ:

ตัวอย่างเหล่านี้แสดงให้เห็นว่าการอ้างอิงตัวเองที่ดูสับสนใน descriptive recursion สามารถแก้ได้ด้วยการแทนชื่อด้วยนิยามซ้ำๆ การแทนนิยามซ้ำนี้ยังใช้ได้กับภาพ recursive ที่แสดงห้องพร้อมทีวีที่โชว์ภาพของห้องนั้นเอง (ดู figure 13.1)

นี่คือก้าวแรกๆ ที่แสดงว่าการแทนค่าซ้ำๆ เปลี่ยน descriptive recursion ให้เป็น unfolded recursion:

แน่นอนว่ากระบวนการแทนค่านี้ไม่ได้จบลง เพราะ recursion นั้นไม่มีขอบเขตและไม่มีกรณีฐาน สถานการณ์นี้เหมือนกับนิยามของลิสต์อนันต์ของค่า 1:

Ones = 1→Ones

เมื่อรันนิยามนี้ การแทนค่าจะสร้างลิสต์ที่ยาวขึ้นเรื่อยๆ ในแต่ละก้าวจะมีการเพิ่ม 1 เข้าไปในลิสต์:

กระบวนการแทนชื่อนิยามซ้ำๆ นี้ยังถูกเรียกว่า rewriting ดังนั้นเมื่อเรามองว่าการเดินทางข้ามเวลาของ Marty เป็นการคำนวณ ก็ถือได้ว่าเขากำลัง rewriting history จริงๆ

A Smaller Footprint (ร่องรอยที่เล็กลง)

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

อย่างไรก็ตาม แม้ substitution trace จะช่วยให้เข้าใจ แต่ก็อาจทำให้ถูกรบกวนเมื่อมันยาวเกินไป พิจารณา insertion sort (ดู chapter 6) ต่อไปนี้เป็นนิยามแบบ recursive ของอัลกอริทึม Isort ซึ่งใช้สองลิสต์ คือ ลิสต์ขององค์ประกอบที่ยังต้องเรียง และลิสต์ขององค์ประกอบที่เรียงแล้ว:

Isort( , list)	\= list
Isort(x_→_rest, list)	\= Isort(rest, Insert(x, list))
Insert(w, )	\= w
Insert(w, x_→_rest)	\= if w ≤ x_ then _w_→_x_→_rest_ else _x_→_Insert(w, rest)

Figure 13.2 Substitution trace for the execution of insertion sort.

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

ตามที่ figure 13.2 แสดง การก่อสร้างของลิสต์ที่เรียงแล้วต้องผ่านหลายขั้นตอน และผลจากการรัน Insert หลายครั้งถูกบดบังบางส่วนด้วยเงื่อนไขและการมีตัวแทนของลิสต์ชั่วคราวสองครั้งในทางเลือกของเงื่อนไข แม้ว่า trace ที่ได้จากการแทนค่านั้นจะแม่นยำและแสดงรายละเอียดที่อัลกอริทึมทำจริง แต่ก็ต้องใช้ความตั้งใจและความสนใจมากในการไล่ดูรายละเอียดทั้งหมดและแยกข้อมูลออกจากคำสั่ง

อีกแง่มุมหนึ่งของวิธีการ substitution ที่อาจทำให้สับสนคือในหลายกรณีการแทนค่าที่ต่างกันสามารถทำได้ และแม้ว่าการเลือกจะไม่เปลี่ยนผลลัพธ์โดยทั่วไป แต่ก็อาจส่งผลต่อขนาดของ trace และความเข้าใจได้ เช่น figure 13.2 แสดงว่าการแทนค่าครั้งแรกให้ผลเป็น Isort(W→H, Insert(B, )), ซึ่งสามารถแทนค่าได้สองทาง: เราอาจใช้สมการข้อแรกสำหรับ Insert หรือใช้สมการข้อที่สองสำหรับ Isort.

Chapter 6 แสดง trace ที่มีเฉพาะข้อมูลเพื่อสาธิตอัลกอริทึมการเรียงต่างๆ: สำหรับแต่ละองค์ประกอบที่ถูกย้าย จะมีเพียงลิสต์ที่ยังไม่เรียงและลิสต์ที่เรียงแล้วเท่านั้นที่ปรากฏ (ดูภาพของ insertion sort ใน figure 6.2) หากเราใช้การแสดงผลแบบเดียวกันกับตัวอย่างที่นี่ เราจะได้ trace ที่สั้นและกระชับกว่ามากเมื่อเทียบกับ figure 13.2:

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

ในขณะที่ trace จากวิธี substitution ทำหน้าที่สองประการ คือ ติดตามวิวัฒนาการของข้อมูลและความคืบหน้าของการคำนวณ interpreter จะใช้ stack data type สำหรับสองงานนี้เป็นการเฉพาะ โดยเฉพาะอย่างยิ่ง สำหรับอัลกอริทึมแบบ recursive interpreter ต้องติดตามสำหรับแต่ละการเรียกซ้ำว่ามันหยุดอยู่ที่จุดใด เพื่อที่จะกลับไปและทำงานต่อหลังจากการเรียกซ้ำสิ้นสุดลง และเนื่องจากแต่ละการรัน recursive ของอัลกอริทึมมีอาร์กิวเมนต์ของตัวเอง interpreter จึงต้องสามารถเก็บหลายเวอร์ชันของพารามิเตอร์ได้

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

Figure 13.3 การตีความของ ToDo(1985) — หากคำสั่งปัจจุบันเป็นการเรียกแบบ recursive ที่อยู่ถัดไปจะถูกจำไว้บนสแตกเพื่อให้สามารถดำเนินการต่อหลังจากการเรียกซ้ำเสร็จสิ้น ซึ่งเกิดขึ้นเมื่อพบคำสั่ง return หลังการกระโดดกลับ ที่อยู่จะถูกนำออกจากสแตก

ToDo(1985) = ① ToDo(1955) ② go camping_ ③ _return

ToDo(1955) = ④ destroy almanac_ ⑤ _ToDo(1885) ⑥ return

ToDo(1885) = ⑦ save Doc_ ⑧ _return

Interpreter รันอัลกอริทึมที่ถูกเรียกด้วยอาร์กิวเมนต์ เช่น ToDo(1985) โดยการทำคำสั่งทีละคำสั่งและเก็บที่อยู่ที่จะกระโดดกลับไว้บนสแตก เมื่อคำสั่งใดเป็นการเรียกแบบ recursive ที่อยู่ที่ตามมาหลังคำสั่งนั้นจะถูก push ขึ้นบนสุดของสแตกก่อนที่ interpreter จะกระโดดไปยังคำสั่งที่เรียก ในตัวอย่าง คำสั่งแรกเป็นการกระโดดที่ทำให้ที่อยู่ถัดไป ② ถูก push ไปบนสแตกและทำให้ ④ เป็นคำสั่งถัดไป

ส่วนนี้แสดงในสองบรรทัดแรกของ figure 13.3 ซึ่งแสดงว่าคำสั่งปัจจุบันและสแตกพัฒนาอย่างไรระหว่างการรัน คอลัมน์ที่สองแสดงสแตกโดยให้บนสุดอยู่ทางซ้ายและก้นสุดอยู่ทางขวา รูปยังแสดงส่วนของโลกที่เปลี่ยนผ่านการรันคำสั่ง เช่น ปีปัจจุบันหรือการครอบครองของ sports almanac ข้อเท็จจริงเฉพาะนี้ของโลกเปลี่ยนหลังจากที่ Marty ทำลาย sports almanac ในปี 1955 อย่างไรก็ตาม ข้อเท็จจริงที่ว่า Doc Brown อยู่ในอันตรายนั้นไม่ใช่ผลลัพธ์จากการรันอัลกอริทึมปัจจุบัน แต่อยู่ในขั้นตอนถัดไปของอัลกอริทึม หลังจากการเดินทางไป 1885 ซึ่งทำให้ที่อยู่กลับ ⑥ ถูก push ขึ้นสแตก การกระทำบันทึก Doc Brown เปลี่ยนข้อเท็จจริงเรื่องการอยู่ในอันตราย จุดถัดไปในอัลกอริทึมคือการ return กลับไปยังตำแหน่งที่อัลกอริทึมหยุดเมื่อกระโดดแบบ recursive ถูกทำ จุดเป้าหมายสำหรับการกระโดดกลับคือที่อยู่สุดท้ายที่ถูก push ขึ้นบนสแตก ดังนั้นการรันคำสั่ง return ทำให้คำสั่งถัดไปเป็นคำสั่งที่ที่อยู่ ⑥ ซึ่งเป็น return อีกคำสั่งที่ยัง pop ที่อยู่กลับออกจากสแตก นี่จึงเผยเป้าหมายสำหรับคำสั่ง return ถัดไป ซึ่งคือ ② จุดที่ Marty และ Jennifer จะสามารถไปตั้งแคมป์ได้

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

เพื่อเรียงลิสต์ของสิ่งของของ Marty interpreter เริ่มประเมินการเรียก Isort(B→W→H, ) ด้วยสแตกว่าง การแมตช์อาร์กิวเมนต์กับรูปแบบพารามิเตอร์ของ Isort ทำให้เกิด bindings ซึ่งเป็นการจับคู่ชื่อพารามิเตอร์ที่ใช้ในรูปแบบกับค่า การจับคู่นี้ถูก push ขึ้นบนสแตก ทำให้เกิดสแตกที่แสดงใน figure 13.4A อาจดูแปลกที่แม้ Isort จะรับอินพุตสองตัว การประยุกต์ใช้งานกับอินพุตตัวแรกที่ไม่ว่างกลับสร้าง bindings สำหรับพารามิเตอร์สามตัวบนสแตก ทั้งนี้เป็นเพราะอาร์กิวเมนต์แรกถูกแมตช์กับรูปแบบ x_→_rest ซึ่งประกอบด้วยสองพารามิเตอร์ที่ใช้แยกรายการอาร์กิวเมนต์เป็นสองส่วน คือ องค์ประกอบแรกและหางของลิสต์ สมการข้อแรกสร้าง binding ให้พารามิเตอร์เพียงตัวเดียวเพราะอินพุตตัวแรกเป็นรายการว่างและไม่จำเป็นต้องถูกอ้างอิงด้วยชื่อ

หลังจากการแมตช์รูปแบบซึ่งสร้าง bindings บนสแตกแล้ว อัลกอริทึมสั่งให้คำนวณ Isort(rest, Insert(x, list)). เช่นเดียวกับวิธี substitution interpreter มีสองทางเลือกในการดำเนินต่อ: หรือจะดำเนินการต่อกับการเรียก Isort ด้านนอก หรือตัดสินใจก่อนจัดการการเรียก Insert ที่ซ้อนอยู่ ภาษาส่วนใหญ่ประเมินอาร์กิวเมนต์ก่อนเรียกใช้อัลกอริทึม ตามแนวทางนี้ interpreter จะประเมิน Insert(x, list) ก่อนจะประเมินการเรียก Isort ค่า x และ list สามารถถูกดึงออกมาจากสแตกและนำไปประเมิน Insert(B, ) การประเมินนี้สามารถทำได้โดยสแตกแยกต่างหากและให้ผลลัพธ์เป็นลิสต์ B ซึ่งหมายความว่าการประเมินการเรียก Isort กลายเป็น Isort(rest, B)

Interpreter ประเมิน Isort(rest, B) โดยใช้สแตกที่แสดงใน figure 13.4A ก่อนอื่นค่าของ rest ถูกดึงจากสแตก ซึ่งหมายความว่า interpreter แท้จริงแล้วกำลังประเมินการเรียก Isort(W→H, B) จากนั้นการแมตช์รูปแบบจะสร้าง bindings ใหม่สำหรับพารามิเตอร์ของ Isort ที่ถูก push ขึ้นบนสแตก ดังที่แสดงใน figure 13.4B

Figure 13.4 Snapshots of stack values during the interpretation of Isort(B→W→H, ).

น่าสังเกตว่า พารามิเตอร์ x, rest, และ list ปรากฏอยู่สองครั้งบนสแตก นี่เป็นเพราะการเรียก Isort แบบ recursive ใช้อาร์กิวเมนต์ที่ต่างกันสำหรับพารามิเตอร์ดังกล่าวและจึงต้องการพื้นที่เก็บแยกต่างหาก เมื่อการเรียก Isort ที่ซ้อนกันผ่านไปแล้ว binding สำหรับพารามิเตอร์ถูกเอาออกจาก ("popped off") สแตก และการคำนวณของการเรียก Isort ก่อนหน้าสามารถดำเนินต่อโดยเข้าถึงอาร์กิวเมนต์ของตัวเองได้

อย่างไรก็ตาม ก่อนที่จะเสร็จสิ้น การเรียก Isort จะนำไปสู่การประยุกต์ใช้สมการข้อที่สองของ Isort อีกครั้ง ซึ่งกระตุ้นการประเมิน Isort(rest, Insert(x, list)) การจับคู่นั้นยังคงถูกเก็บบนสแตก แต่เนื่องจากมี binding หลายชุดสำหรับแต่ละชื่อพารามิเตอร์ คำถามคือควรใช้ binding ชุดใดและจะหาได้อย่างไร นี่คือที่ที่สแตกเข้ามามีบทบาทอีกครั้ง เนื่องจากค่าพารามิเตอร์สำหรับการเรียก Isort ล่าสุดถูก push ขึ้นสแตกล่าสุด พวกมันจึงอยู่บนสุดของสแตก การเรียกที่ตามมาจึงกลายเป็น Isort(H,Insert(W, B)) เนื่องจาก Insert(W, B) ให้ผลเป็น B→W การเรียก Isort ถัดไปที่จะถูกประเมินคือ Isort(H, B→W) ซึ่งกระตุ้นสมการข้อที่สองของ Isort อีกครั้ง และนำไปสู่การเรียกอีกครั้ง Isort(rest, Insert(x,list)) พร้อมสแตกที่แสดงใน figure 13.4C

การค้นหาค่าพารามิเตอร์จากบนสุดของสแตกแล้วนำไปประเมิน ทำให้การเรียกนี้นำไปสู่การประเมิน Isort( ,Insert(H,B)) ซึ่งต่อมาให้ผลเป็น Isort( , B→H→W) หลังการประเมิน Insert(H, B→W) เนื่องจากตอนนี้อาร์กิวเมนต์ตัวแรกของ Isort เป็นรายการว่าง interpreter จึงให้ค่า list มาประเมินโดยสมการข้อแรกของ Isort การประเมินนี้เกิดขึ้นในบริบทของสแตกที่แสดงใน Figure 13.4D

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

สแตกที่เป็นตัวแทนการซ้อนของการเรียก Isort ทั้งหมด (figure 13.4D) เพียงพอที่จะสร้าง trace สองลิสต์ดังกล่าวโดยระบบ เฉพาะแต่ละกลุ่มของการจับคู่บนสแตกจะให้หนึ่งก้าวของ trace จำได้ว่าทุกอินพุตที่ไม่ว่างของ Isort ถูกแยกเมื่อ Isort ถูกเรียกเพื่อสร้าง bindings สำหรับพารามิเตอร์สองตัว x และ rest. นั่นหมายความว่า อินพุตสำหรับสามการเรียกแรกของ Isort ถูกกำหนดโดยรายการ x_→_rest และผลลัพธ์กำหนดโดย list. สำหรับการเรียกสุดท้ายของ Isort เมื่ออินพุตเป็นรายการว่าง อินพุตจะเป็นรายการว่างซึ่งไม่ถูกผูกกับพารามิเตอร์ และผลลัพธ์คือ list. ดังนั้นรายการด้านล่างของสแตกให้คู่ของลิสต์ B→W→H และรายการว่าง รายการที่สองให้ W→H และ B รายการที่สามให้ H และ B→W และรายการบนสุดให้รายการว่าง (อินพุต ไม่ได้ถูกผูกกับพารามิเตอร์) และ B→H→W

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

Doppelgängers Get More Done (การมี Doppelgängers ทำให้ทำงานได้มากขึ้น)

เมื่อ Marty กลับไปปี 1955 เป็นครั้งที่สอง (หลังจากกลับมาพร้อมกับ Doc จากปี 2015 ไปยัง 1985 ที่มีความรุนแรง) เขาจะมีอยู่ในปี 1955 สองคน เพราะอดีตที่เขากำลังย้อนกลับไปคืออดีตที่เขาเคยเดินทางไปมาก่อน (โดยบังเอิญในหนังภาคแรก) Martys ทั้งสองไม่โต้ตอบกันและทำสิ่งต่างกัน Marty คนแรกพยายามให้พ่อแม่ของเขาตกหลุมรัก ในขณะที่ Marty คนที่สองพยายามเอา sports almanac ไปจาก Biff ในทำนองเดียวกัน เมื่อ Biff แก่เดินทางจาก 2015 ไป 1955 เพื่อให้หนังสือพยากรณ์แก่ตัวเองในวัยหนุ่ม เขาก็มีอยู่สองคนในปี 1955 แตกต่างจากสอง Marty สอง Biff กลับมีปฏิสัมพันธ์กัน Old Biff ให้ young Biff sports almanac โชคดีที่พาราด็อกซ์เวลาอาจเกิดขึ้นซึ่งอาจทำให้จักรวาลถูกทำลายยังไม่เกิดขึ้น ยิ่งไปกว่านั้น เครื่องย้อนเวลาที่ Marty ใช้จาก 1985 ไป 1955 ก็เป็นเครื่องเดียวกับที่ Old Biff ใช้จาก 2015 ไป 1955 ดังนั้น ณ เวลาที่ Marty เห็นว่า Old Biff ให้ young Biff sports almanac ต้องมีเครื่องย้อนเวลาอยู่ 2 เครื่องในปี 1955 แท้จริงแล้วต้องมี สาม เครื่อง เนื่องจาก Marty คนแรกก็มาในปี 1955 พร้อมกับเครื่องย้อนเวลาเช่นกัน

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

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

Quicksort และ mergesort เป็นตัวอย่างของอัลกอริทึมดังกล่าว (ดู chapter 6) นิยามของ quicksort เป็นดังนี้ สมการข้อแรกบอกว่าลิสต์ว่างเรียงแล้ว และสมการข้อที่สองบอกว่าเพื่อเรียงลิสต์ที่ไม่ว่างให้เอาองค์ประกอบทั้งหมดจากหางของลิสต์ (rest) ที่มีค่าน้อยกว่า x มาเรียงและวางไว้หน้าตัว x และในทำนองเดียวกันให้นำผลของการเรียงองค์ประกอบที่มากกว่าหรือเท่ากับ x มาไว้หลัง x:

Qsort( )	\=
Qsort(x_→_rest)	\= Qsort(Smaller(rest, x))→x_→_Qsort(Larger(rest, x))

สังเกตว่าสมการข้อที่สองแสดง nonlinear recursion ของ Qsort. Quicksort ทำงานได้ดีเมื่อ x ทำให้หางแยกออกเป็นสองลิสต์ย่อยที่มีขนาดใกล้เคียงกันซ้ำๆ ซึ่งอาจไม่เกิดขึ้นในกรณีที่แย่ที่สุดเมื่อรายการเรียงอยู่แล้ว แต่ quicksort ทำงานได้ดีมากเฉลี่ย

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