LATEST

Đệ 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ì?

Đệ quy đuôi là một hàm thực hiện gọi đệ quy ở sau cùng. Nói một cách dễ hiểu thì hàm đệ quy đuôi sẽ có câu lệnh gọi lại chính nó ở cuối hàm. Một hàm đệ quy đuôi có thể gọi một hoặc nhiều lần đệ quy trong hàm.

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.

bai18 01 png

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

bai18 02 png

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

bai18 03 png

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

bai18 04 png

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

Cùng chuyên mục:

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tìm ước chung lớn nhất trong C / C++

Thuật toán tìm ước chung lớn nhất trong C / C++

Top