Đệ quy đuôi (Tail Recursion) - Giải thuật đệ quy

Trong bài này mình sẽ giới thiệu đến các bạn một trong các hàm đệ quy tiếp theo, đó là hàm đệ quy đuôi (Tail Recursion). Đây là một hàm đệ quy cơ bản và được sử dụng khá nhiều trong lập trình.

Chúng ta sẽ cùng nhau tìm hiểu về đệ quy đuôi là gì? và cơ chế hoạt động của đệ quy đuôi như thế nào thông qua 2 ví dụ.

1. Đệ quy đuôi là gì?

Đệ quy đuôi là một trường hợp đặc biệt của đệ quy tuyến tính. Giống như tên của nó, đệ quy đuôi là hàm thực hiện gọi đệ quy ở sau cùng.

Trong hàm đệ quy đuôi có thể gọi nhiều lần chính nó, nó có dạng tương tự như 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);
}

Đây là hàm tìm ước số chung lớn nhất sử dụng đệ quy đuôi để thực hiện. Như các bạn thấy trong hàm này gọi lại chính nó 2 lần và kết thúc hàm gọi lại chính đệ quy đó.

2. Cơ chế hoạt động đệ quy đuôi

Ở phần này mình sẽ lấy hàm đệ quy UCLN() để chạy hai ví dụ với hai tham số khác nhau, để các bạn hiểu rõ hơn về cơ chế hoạt động của đệ quy đuôi.

Hà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);
}

Ví dụ 1

Trong ví dụ này mình sẽ lấy tham số truyền vào cho hàm UCLN() là m = 25 và n = 5, cụ thể như hình dưới đây:

Trong trường hợp này hàm chỉ thực hiện một lần và không gọi chính nó lần nào nên không có kết quả nào được đẩy vào Stack.

Code mẫu:

#include <iostream>
using namespace std;

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() {
  int kq,m,n;
  cout<<"Nhập m: ";
  cin>>m;
  cout<<"Nhập n: ";
  cin>>n;
  kq = UCLN(m,n);
  cout<<"Kết quả: "<<kq;
  cout<<"
--------------------------
";
  cout<<"Chương trình này được đăng tại Zaidap.com.net";
}

Kết quả:

Ví dụ 2

Cũng là hàm UCLN(), nhưng lần này mình sẽ truyền vào tham số m = 5 và n = 25. Hãy cùng xem cơ chế hoạt động của hàm lúc này sẽ như thế nào nhé:

*Lưu ý: Các bạn sẽ dễ hiểu nhầm rằng hàm đã kết thúc ở bước gọi đệ quy lần hai sau khi return n -> 5. Nhưng trong Stack vẫn còn giá trị, vì vậy phải gọi Stack và thực hiện cho đến khi trong Stack rỗng.

Kết quả:

3. Kết luận

Thông qua hai ví dụ trên, đã biểu diễn cơ chế hoạt động của đệ quy đuôi rất rõ ràng. Các bạn có thể thấy cả hai ví dụ đều cho về cùng một kết quả, nhưng cách thức nó hoạt động lại khác nhau hoàn toàn. Vì vậy các bạn phải nắm thật kỹ các bước gọi hàm, chạy hàm, xét điều kiện và return kết quả. Nếu thiếu một bước nào đó có thể dẫn đến bài toán sai. Chúc các bạn thực hiện thành công!!!