การวนซ้ำ

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

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

 คณิตศาสตร์ 

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

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

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

 การนำไปใช้งาน 
วงวน (loop) เป็นโครงสร้างของภาษาโปรแกรมที่ใช้ในการวนซ้ำได้บ่อยที่สุด โค้ดเทียมต่อไปนี้แสดงการวนซ้ำคำสั่งระหว่าง begin และ end จำนวนสามครั้งด้วย for loop โดยใช้ค่าของตัวแปร i เป็นตัวเพิ่มค่าในแต่ละรอบ

a := 0
for i := 1 to 3 do       { loop three times }
begin
    a := a + i;          { add the current value of i to a }
end;
print(a);                { the number 6 is printed (0 + 1; 1 + 2; 3 + 3) }

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

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

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

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

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

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

โค้ดด้านล่างเป็นตัวอย่างของขั้นตอนวิธีแบบเวียนเกิดที่เขียนด้วยภาษาสกีม โดยโค้ดนี้ให้ผลลัพธ์เหมือนกับโค้ดเทียมที่แสดงไว้ในหัวข้อก่อนหน้า
(let iterate ((i 1) (a 0))
  (if (<= i 3)
    (iterate (+ i 1) (+ a i))
    (display a)))

 การศึกษา 

ในบางสำนักของครุศาสตร์ (pedagogy) มีการใช้การทำซ้ำ (iteration) เพื่ออธิบายกระบวนการสอนหรือการชี้แนะให้นักเรียนทำการทดลอง การประเมิน หรือโครงการซ้ำ ๆ จนกว่าจะพบผลลัพธ์ที่แม่นยำยิ่งขึ้น หรือจนกว่านักเรียนจะเกิดความเชี่ยวชาญในทักษะทางเทคนิคนั้น แนวคิดนี้ปรากฏอยู่ในภาษิตโบราณที่ว่า "การฝึกฝนทำให้เกิดความสมบูรณ์แบบ" (Practice makes perfect) โดยเฉพาะอย่างยิ่ง คำว่า "iterative" ถูกนิยามว่าเป็น "กระบวนการเรียนรู้และพัฒนาที่เกี่ยวข้องกับการสอบถามเป็นวัฏจักร ซึ่งเปิดโอกาสให้ผู้คนได้กลับไปทบทวนความคิดและสะท้อนมุมมองต่อผลกระทบที่เกิดขึ้นอย่างมีวิจารณญาณ" 

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

 ดูเพิ่ม 
 การเวียนเกิด (Recursion)
 แฟรกทัล (Fractal)
 การค้นหาแบบบรูตฟอร์ซ (Brute-force search)
 ฟังก์ชันทำซ้ำ (Iterated function)
 การประกอบฟังก์ชันวิเคราะห์ไม่สิ้นสุด (Infinite compositions of analytic functions)

 อ้างอิง 

หมวดหมู่:การบริหารเวลา
หมวดหมู่:แฟร็กทัล
หมวดหมู่:ขั้นตอนวิธี