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

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

ตัวอย่าง

#include <iostream>
using namespace std;
void printN(int n){
   if(n < 0){
      return;
   }
   cout << n << " ";
   printN(n - 1);
}
int main() {
   printN(10);
}

ผลลัพธ์

10 9 8 7 6 5 4 3 2 1 0

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

เราสามารถใช้แฟกทอเรียลโดยใช้การเรียกซ้ำ แต่ฟังก์ชันไม่ใช่การเรียกซ้ำส่วนท้าย ค่าของ fact(n-1) ถูกใช้ใน fact(n)

long fact(int n){
   if(n <= 1)
      return 1;
   n * fact(n-1);
}

เราสามารถทำให้เป็นแบบเรียกซ้ำได้ โดยการเพิ่มพารามิเตอร์อื่นๆ นี่คือด้านล่าง −

long fact(long n, long a){
   if(n == 0)
      return a;
   return fact(n-1, a*n);
}