Ở đây chúng ta sẽ xem đệ quy đuôi là gì. Đệ quy đuôi về cơ bản là sử dụng hàm đệ quy làm câu lệnh cuối cùng của hàm. Vì vậy, khi không còn gì để làm sau khi quay lại từ cuộc gọi đệ quy, đó được gọi là đệ quy đuôi. Chúng ta sẽ thấy một ví dụ về đệ quy đuôi.
Ví dụ
#include <iostream>
using namespace std;
void printN(int n){
if(n < 0){
return;
}
cout << n << " ";
printN(n - 1);
}
int main() {
printN(10);
} Đầu ra
10 9 8 7 6 5 4 3 2 1 0
Đệ quy đuôi tốt hơn đệ quy không đuôi. Vì không còn tác vụ nào sau cuộc gọi đệ quy, trình biên dịch sẽ dễ dàng tối ưu hóa mã hơn. Khi một hàm được gọi, địa chỉ của nó được lưu trữ bên trong ngăn xếp. Vì vậy, nếu nó là đệ quy đuôi, thì không cần lưu trữ các địa chỉ vào ngăn xếp.
Chúng ta có thể sử dụng giai thừa bằng cách sử dụng đệ quy, nhưng hàm không phải là đệ quy đuôi. Giá trị của fact (n-1) được sử dụng bên trong fact (n).
long fact(int n){
if(n <= 1)
return 1;
n * fact(n-1);
} Chúng ta có thể làm cho nó đuôi đệ quy, bằng cách thêm một số tham số khác. Điều này giống như bên dưới -
long fact(long n, long a){
if(n == 0)
return a;
return fact(n-1, a*n);
}