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

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

การเรียกซ้ำเป็นหนึ่งในแนวคิดหลักของวิทยาการคอมพิวเตอร์ แต่ยิ่งกว่านั้นในอัลกอริทึม ในบทความนี้ผมจะพูดถึงการเรียกซ้ำที่เกี่ยวข้องกับอัลกอริทึม โดยทั่วไปมีสองวิธีในการแก้ปัญหาอัลกอริธึมแบบวนซ้ำหรือแบบเรียกซ้ำ การเรียกซ้ำใช้ในอัลกอริธึม Dom traversal, Object/Hash traversal, Depth-first search traversal (DFS), Breadth-first search traversal (BFS) เป็นต้น

สแต็กการโทร:

การเรียกซ้ำใช้สิ่งที่เรียกว่า call stack เมื่อฟังก์ชันเรียกตัวเอง ฟังก์ชันจะเข้าสู่สแต็ก และเมื่อการเรียกซ้ำกระทบกรณีฐาน ฟังก์ชันจะเด้งออกจากสแต็กทีละครั้ง Stack เป็นโครงสร้างข้อมูลที่ใช้เข้าก่อนออกก่อน (LIFO) คล้ายกับแผ่นเรียงซ้อน เมื่อถอดออก คุณต้องนำออกจากด้านบน

กรณีฐาน:

สิ่งหนึ่งที่น่ากลัวถ้าคุณไม่เคยสัมผัสมันมาก่อนคือการเข้าสู่วงจรที่ไม่มีที่สิ้นสุดและไม่รู้ว่าจะปิดมันอย่างไร สิ่งที่น่ากลัวอีกอย่างหนึ่งที่เกี่ยวข้องกับสิ่งนั้นคือกองล้น สิ่งที่เกิดขึ้นคือฟังก์ชันจะเรียกตัวเองอย่างต่อเนื่องและไม่เคยหยุดเรียกตัวเองเลย! เคล็ดลับสำหรับมือโปร: กด ctrl c ข้อผิดพลาด stack overflow สามารถเกิดขึ้นได้ในโปรแกรมคอมพิวเตอร์เนื่องจากการใช้หน่วยความจำมากเกินไป การใช้หน่วยความจำมากเกินไปนี้เกิดขึ้นใน call stack ซึ่งเป็นที่เก็บข้อมูลที่เกี่ยวข้องกับรูทีนย่อยที่แอ็คทีฟในโปรแกรม call stack มีหน่วยความจำที่จำกัด ขนาดจะขึ้นอยู่กับภาษาการเขียนโปรแกรม สถาปัตยกรรม การทำงานแบบมัลติเธรดบน CPU หรือไม่ และมีหน่วยความจำเท่าใด นอกจากนั้น คุณจะเจอข้อผิดพลาด stack overflow หากคุณไม่มีตัวพิมพ์พื้นฐานในฟังก์ชันการเรียกซ้ำ และอาจจำเป็นต้องไปที่stackoverflow.comเพื่อดูว่ามันหมายถึงอะไร คุณสามารถนึกถึงกรณีพื้นฐานที่การโทรสิ้นสุด/หยุด หลังจากที่คุณกดกรณีฐานแล้ว คุณสามารถย้อนกลับได้จนกว่าคุณจะกลับสู่การเรียกใช้ฟังก์ชันเริ่มต้น

Algos ที่ใช้การเรียกซ้ำ

มาดูกันว่าคำถามประเภทใดที่ได้รับการแก้ไขแบบวนซ้ำ สิ่งที่คุณอาจเห็นว่าใช้บ่อยคือลำดับ Fibonacci โดยที่ตัวเลขแต่ละตัวในลำดับคือผลรวมของตัวเลขสองตัวที่อยู่ข้างหน้า ลำดับคือ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 เป็นต้น คุณอาจถูกขอให้แก้ไขหมายเลข fib ที่ n และคุณอาจต้องการใช้การเรียกซ้ำเพื่อแก้ปัญหานี้

ลำดับฟีโบนักชี

function fib(n){
  if (n <= 2) return 1;
  return fib(n-1) + fib(n-2);
}
console.log(fib(10))

function reverse(str){
 if(str.length <= 1) return str;
 return reverse(str.slice(1)) + str[0];
}
// reverse('awesome') // 'emosewa'