Đệ quy đuôi (Tail Recursion) trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn hàm đệ quy đuôi (Tail Recursion) trong C / C++. Đây là một trong các loại hàm đệ quy cơ bản trong C / C++, được sử dụng khá nhiều trong các bài toán đơn giản.

Chúng ta sẽ lần lượt tìm hiểu về đệ quy đuôi (Tail Recursion) là gì? Cơ chế hoạt động của nó. Sau đó là một vài ví dụ về cách sử dụng nó trong C / C++.

Đệ quy đuôi (Tail Recursion) trong C / C++ là gì?

Ví dụ mình có hàm đệ quy đuối tìm UCLN trong C / C++ dưới đây:

int UCLN(int m, int n){
  int r;
  if(m<n) return UCLN(n,m);
  r = m % n;
  if(r == 0) return n;
  else return UCLN(n,r);
}

Như các bạn thấy, hàm trên thực hiện gọi đệ quy hai lần. Và ở cuối hàm, có lệnh gọi đệ quy. Như vậy thì đây chính là hàm đệ quy đuôi.

Để hiểu rõ hơn, các bạn hãy qua phần tiếp theo tìm hiểu về cơ chế hoạt động của nó nhé.

Cơ chế hoạt động của đệ quy đuôi (Tail Recursion) trong C / C++

Cơ chế hoạt động của đệ quy đuôi (Tail Recursion) trong C / C++ cũng hoạt động theo cơ chế LIFO (hay còn gọi là cơ chế Stack). Vậy nó hoạt động cụ thể như thế nào, các bạn hãy cùng mình xem hai ví dụ dưới đây.

Giả sử mình có hàm đệ quy đuôi tìm UCLN của hai số m và n.

int UCLN(int m, int n){
  int r;
  if(m<n) return UCLN(n,m);
  r = m % n;
  if(r == 0) return n;
  else return UCLN(n,r);
}

Ví dụ 1: Mình lấy giá trị m = 25 và n = 5, khi đó hàm đệ quy sẽ hoạt động như sau.

Trong trường hợp trên, vì m > n nên điều kiện m < n sai, thuật toán sẽ chạy câu lệnh r = m % n.

Lúc này r = 0, vậy nên thuật toán trả về n = 5. Hàm không thực hiện gọi đệ quy nên sẽ không có kết quả được lưu trong Stack. Đến đây thì hàm đã chính thức kết thúc.

Ví dụ 2: Mình lấy giá trị m = 5 và n = 25, các bạn hay so sánh xem có gì khác với ví dụ trên nhé.

Tại bước số hai, khi return 5 thì các bạn sẽ nghĩ đây là kết quả cuối cùng rồi. Tuy nhiên trong Stack vẫn còn giá trị, nên cần gọi trong Stack cho đến khi nó rỗng. Khi đó hàm mới chính thức kết thúc.

Ví dụ sử dụng đệ quy đuôi (Tail Recursion) trong C / C++

Trong phần này, mình sẽ thực hiện chương trình tìm ước chung lớn nhất của hai số được nhập từ bàn phím. Bằng cách sử dụng hàm đệ quy đuôi (Tail Recursion) trong C / C++.

Đầu tiên chúng ta tạo hàm tính UCLN() thuộc dạng đệ quy đuôi (Tail Recursion) trong C / C++. Hàm có hai tham số truyền vào là m và n.

int UCLN(int m, int n){
  int r;
  if(m<n) return UCLN(n,m);
  r = m % n;
  if(r == 0) return n;
  else return UCLN(n,r);
}

Tiếp đến ta khai báo và yêu cầu người dùng nhập vào hai số nguyên m và n. Hai số này chính là tham số để truyền vào hàm đệ quy tìm UCLN.

//khai báo các biến là các giá trị cần tính
  int kq,m,n;
  //yêu cầu ngươi dùng nhập vào hai giá trị cầm tính
  cout<<"Nhập giá trị m: ";
  cin>>m;
  cout<<"Nhập giá trị n: ";
  cin>>n;

Sau đó gọi hàm UCLN() để tìm và gán kết quả tìm được cho biến kq. Hiển thị kết quả ra màn hình cho người dùng xem.

//gọi hàm UCLN để tìm rồi gán cho biến kq
  kq = UCLN(m,n);
  //hiển thị kết quả ra màn hình
  cout<<"Kết quả: "<<kq;

Dưới đây là hai chương trình mình đã viết sẵn bằng hai ngôn ngữ C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>

int UCLN(int m, int n){
  int r;
  if(m<n) return UCLN(n,m);
  r = m % n;
  if(r == 0) return n;
  else return UCLN(n,r);
}
 
int main(void) {
  int kq,m,n;
  printf("Nhập giá trị m: ");
  scanf("%d", &m);
  printf("Nhập giá trị n: ");
  scanf("%d", &n);
  kq = UCLN(m,n);
  printf("Kết quả: %d",kq);

  printf("\n---------------------------------\n");
  printf("Chương trình này được đăng tại codehow.net");
  return 0;  
}

Kết quả:

Chương trình C++:

#include <iostream>
using namespace std;
//tạo hàm tìm UCLN
int UCLN(int m, int n){
  int r;
  if(m<n) return UCLN(n,m);
  r = m % n;
  if(r == 0) return n;
  else return UCLN(n,r);
}
 
int main() {
  //khai báo các biến là các giá trị cần tính
  int kq,m,n;
  //yêu cầu ngươi dùng nhập vào hai giá trị cầm tính
  cout<<"Nhập giá trị m: ";
  cin>>m;
  cout<<"Nhập giá trị n: ";
  cin>>n;
  //gọi hàm UCLN để tìm rồi gán cho biến kq
  kq = UCLN(m,n);
  //hiển thị kết quả ra màn hình
  cout<<"Kết quả: "<<kq;
  cout<<"\n--------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Kết luận

Như vậy là chúng ta đã cùng nhau tìm hiểu về đệ quy đuôi (Tail Recursion) trong C / C++. Qua bài viết này các bạn cần nắm các kiến thức sau đây:

• Đệ quy đuôi là hàm gọi đệ quy ở sau cùng.
• Một hàm đệ quy đuôi có thể gọi đệ quy nhiều lần trong thân hàm.
• Cơ chế hoạt động của hàm đệ quy đuôi dựa vào cơ chế LIFO.
• Ví dụ sử dụng hàm đệ quy đuôi là tìm ước chúng lớn nhất.

Ở bài viết tiếp theo, mình sẽ giới thiệu đến các bạn hàm đệ quy nhị phân trong C / C++, các bạn chú ý theo dõi nhé !!!