หลักการเรียกซ้ำในโครงสร้างข้อมูล

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

ฟังก์ชันแบบเรียกซ้ำมีสองส่วนที่แตกต่างกัน กรณีฐานและกรณีแบบเรียกซ้ำ กรณีพื้นฐานใช้เพื่อยุติงานที่เกิดซ้ำ หากไม่ได้กำหนดตัวพิมพ์พื้นฐาน ฟังก์ชันจะเกิดขึ้นซ้ำไม่จำกัดจำนวนครั้ง (ตามทฤษฎี)

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

ตัวอย่างหนึ่งของการโทรแบบเรียกซ้ำคือการค้นหาแฟกทอเรียลของตัวเลข จะเห็นว่าแฟกทอเรียลของจำนวน n =n! เหมือนกับ n * (n-1)! และเหมือนกับ n * (n - 1) * (n - 2)! ดังนั้นหากแฟกทอเรียลเป็นฟังก์ชัน มันจะถูกเรียกครั้งแล้วครั้งเล่า แต่อาร์กิวเมนต์ลดลง 1 เมื่ออาร์กิวเมนต์เป็น 1 หรือ 0 อาร์กิวเมนต์จะส่งกลับ 1 นี่อาจเป็นกรณีพื้นฐานของการเรียกซ้ำ

ตัวอย่าง

#include<iostream>
using namespace std;
long fact(long n){
   if(n <= 1)
   return 1;
   return n * fact(n-1);
}
main(){
   cout << "Factorial of 6: " << fact(6);
}

ผลลัพธ์

Factorial of 6: 720