Recursion. A method can call itself

Recursion. A method can call itself (if you are not comfortable with this idea, known
as recursion, you are encouraged to work Exercises 1.1.16 through 1.1.22). For example,
the code at the bottom of this page gives an alternate implementation of the
rank() method in BinarySearch. We often use recursive implementations of methods
because they can lead to compact, elegant code that is easier to understand than a corresponding
implementation that does not use recursion. For example, the comment
in the implementation below provides a succinct description of what the code is supposed
to do. We can use this comment to convince ourselves that it operates correctly,
by mathematical induction. We will expand on this topic and provide such a proof for
binary search in Section 3.1. There are three important rules of thumb in developing
recursive programs:
■
The recursion has a base case—we always include a conditional statement as the
first statement in the program that has a return.
■ Recursive calls must address subproblems that are smaller in some sense, so
that recursive calls converge to the base case. In the code below, the difference
between the values of the fourth and the third arguments always decreases.
■ Recursive calls should not address subproblems that overlap. In the code below,
the portions of the array referenced by the two subproblems are disjoint.
Violating any of these guidelines is likely to lead to incorrect results or a spectacularly
inefficient program (see Exercises 1.1.19 and 1.1.27). Adhering to them is likely to
lead to a clear and correct program whose performance is easy to understand. Another
reason to use recursive methods is that they lead to mathematical models that we can
use to understand performance. We address this issue for binary search in Section 3.2
and in several other instances throughout the book.

ผลลัพธ์ (ไทย) 1:

สอบ วิธีการสามารถเรียกตัวเอง (ถ้าคุณไม่สะดวกสบายกับความคิดนี้ เรียกว่าเป็นสอบ พร้อมให้ท่านทำงานออกกำลังกาย 1.1.16 ผ่าน 1.1.22) ตัวอย่างรหัสที่ด้านล่างของหน้านี้ให้ดำเนินการอื่นวิธีการ rank() ใน BinarySearch เรามักจะใช้วิธีการใช้งานซ้ำเนื่องจากพวกเขาสามารถนำรหัสกระชับ บริการที่ง่ายต่อการเข้าใจมากกว่าการการใช้งานที่ใช้สอบ ตัวอย่างเช่น ข้อคิดเห็นในการดำเนินการด้านล่างนี้อธิบายรวบรัดอะไรรหัสควรจะทำ เราสามารถใช้คิดการโน้มน้าวใจตัวเองที่มันทำงานได้อย่างถูกต้องโดยเหนี่ยวนำคณิตศาสตร์ เราจะขยายในหัวข้อนี้ และให้หลักฐานดังกล่าวในค้นหาแบบไบนารีในหัวข้อ 3.1 มีสามสิ่งสำคัญกฎของนิ้วหัวแม่มือในการพัฒนาโปรแกรมซ้ำ:■สอบได้กรณีพื้นฐาน — เราจะรวมคำสั่งแบบมีเงื่อนไขเป็นการคำสั่งแรกในโปรแกรมที่มีการส่งคืน■การเรียกซ้ำต้อง subproblems ที่มีขนาดเล็กในความรู้สึกบางอย่าง ดังนั้นที่เรียกซ้ำมาบรรจบกันกับกรณีพื้นฐาน ในโค้ดด้านล่าง ความแตกต่างระหว่างค่าของวันที่สี่และที่สาม อาร์กิวเมนต์จะลดลง■การเรียกซ้ำควร subproblems ที่ทับซ้อนกัน ในโค้ดด้านล่างบางส่วนของอาร์เรย์ที่อ้างอิง โดย subproblems สองตัวได้ละเมิดของแนวทางเหล่านี้จะนำไปสู่ผลลัพธ์ที่ไม่ถูกต้องหรือภาพโปรแกรมต่ำ (ดูฝึก 1.1.19 และ 1.1.27) พวกเขายึดมั่นเป็นแนวโน้มที่จะทำให้โปรแกรมชัดเจน และถูกต้องที่มีประสิทธิภาพคือเข้าใจง่าย อีกเหตุผลในการใช้วิธีการเกิดซ้ำคือ ว่า พวกเขาทำแบบจำลองทางคณิตศาสตร์ที่เราสามารถการเข้าใจประสิทธิภาพ เราแก้ไขปัญหานี้สำหรับการค้นหาแบบไบนารีในหัวข้อ 3.2และ ในหลายกรณีอื่น ๆ ตลอดเล่ม

ผลลัพธ์ (ไทย) 2:

เรียกซ้ำ วิธีที่สามารถเรียกตัวเอง
(ถ้าคุณไม่พอใจกับความคิดนี้เป็นที่รู้จักกันเป็นrecursion คุณได้รับการสนับสนุนในการทำงานผ่านการออกกำลังกาย 1.1.16 1.1.22) ตัวอย่างเช่นรหัสที่ด้านล่างของหน้านี้จะช่วยให้การดำเนินการอื่นของอันดับ() วิธีการใน binarySearch เรามักจะใช้การใช้วิธีการเวียนเกิดเพราะพวกเขาสามารถนำไปสู่การที่มีขนาดกะทัดรัดรหัสสง่างามที่เป็นเรื่องง่ายที่จะเข้าใจกว่าที่สอดคล้องการดำเนินการที่ไม่ได้ใช้การเรียกซ้ำ ยกตัวอย่างเช่นการแสดงความคิดเห็นในการดำเนินการดังต่อไปนี้ให้คำอธิบายสั้นของสิ่งรหัสควรจะทำอย่างไร เราสามารถใช้ความคิดเห็นนี้ที่จะโน้มน้าวตัวเองว่าจะดำเนินการอย่างถูกต้องโดยอุปนัยทางคณิตศาสตร์ เราจะขยายในหัวข้อนี้และให้บริการดังกล่าวหลักฐานสำหรับการค้นหาแบบไบนารีในข้อ 3.1 มีสามกฎที่สำคัญของหัวแม่มือในการพัฒนาเป็นโปรแกรม recursive: ■เรียกซ้ำได้กรณีที่เราฐานเสมอรวมคำสั่งเงื่อนไขเป็นคำสั่งแรกในโปรแกรมที่มีผลตอบแทน. ■โทรซ้ำต้องอยู่ subproblems ที่มีขนาดเล็กในความรู้สึกบาง ดังนั้นที่โทรrecursive บรรจบกับกรณีฐาน ในโค้ดด้านล่างความแตกต่างระหว่างค่าที่สี่และข้อโต้แย้งที่สามมักจะลดลง. ■โทรซ้ำไม่ควรอยู่ subproblems ที่ทับซ้อน ในโค้ดด้านล่างส่วนของอาร์เรย์อ้างอิงโดยทั้งสอง subproblems มีเคล็ด. ละเมิดใด ๆ ของคำแนะนำเหล่านี้มีแนวโน้มที่จะนำไปสู่ผลลัพธ์ที่ไม่ถูกต้องหรือไม่ยี่หระโปรแกรมที่ไม่มีประสิทธิภาพ(ดูการออกกำลังกาย 1.1.19 และ 1.1.27) ยึดมั่นในพวกเขามีแนวโน้มที่จะนำไปสู่การที่ชัดเจนและโปรแกรมที่ถูกต้องมีประสิทธิภาพการทำงานที่ง่ายต่อการเข้าใจ อีกเหตุผลที่จะใช้วิธีการเวียนเกิดที่พวกเขานำไปสู่แบบจำลองทางคณิตศาสตร์ที่เราสามารถใช้ในการทำความเข้าใจการปฏิบัติงาน เราแก้ไขปัญหาสำหรับการค้นหาแบบไบนารีในมาตรา 3.2 และในกรณีอื่น ๆ อีกหลายตลอดทั้งเล่ม