GIẢI THUẬT ĐỆ QUY
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

Đệ quy đuôi (Tail Recursion)

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ụ.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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:

co che de quy duoi PNG

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<<"\n--------------------------\n";
  cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả:

de qui duoi 1 PNG

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é:

co che de quy duoi 1 PNG

*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ả:

de qui duoi 2 PNG

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!!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top