Đệ quy tương hỗ (Mutual Recursion) - Giải thuật đệ quy

Trong bài này mình sẽ giới thiệu các bạn một hàm đệ quy cuối cùng trong các hàm đệ quy cơ bản đó chính là đệ quy tương hỗ (Mutual Recursion).

Chúng ta sẽ cùng nhau tìm hiểu về đệ quy tương hỗ là gì? hoạt động như thế nào?

1. Đệ quy tương hỗ là gì?

Đệ quy tương hỗ là loại đệ quy không gọi đệ quy trực tiếp chính nó, mà gọi một hàm khác. Trong hàm khác lại gọi lại nó. Ví dụ chúng ta có hàm A() gọi đệ quy hàm B() và trong hàm B() gọi lại đệ quy hàm A().

Ta có đệ quy tương hỗ như sau:

bool isEven(int n);
bool isOdd(int n);

bool isEven(int n){
  if(n == 0)
    return true;
  else 
    return isOdd(n - 1);
}

bool isOdd(int n){
  return !isEven(n);
}

Ở trên chúng ta có hai hàm là hàm isEven() và hàm isOdd(). Hai hàm này gọi đệ quy qua lại lẫn nhau, như vậy đây là hai hàm tương hỗ.

Để hiểu hơn chúng ta cùng xem cơ chế hoạt động của nó như thế nào nhé.

2. Cơ chế đệ quy tương hỗ (Mutual Recursion)

Trong phần này mình sẽ sử dụng hai hàm trên để kiểm tra một số n nhập và là số chẵn hay số lẻ. Thực ra bài toán này không cần sử dụng hàm đệ quy, nhưng vì đây là một bài toán đơn giản nên mình sử dụng nó để các bạn dễ nắm bắt hơn.

Như các bạn đã biết thì số chẵn là số chia hết cho 2 (2n) và số lẻ là số chia cho 2 dư 1 (2n - 1).

Để kiểm tra số n là số chẵn hay số lẻ sử dụng hàm đệ quy, ta có hàm đệ quy như sau:

bool isEven(int n);
bool isOdd(int n);

bool isEven(int n){
  if(n == 0)
    return true;
  else 
    return isOdd(n - 1);
}

bool isOdd(int n){
  return !isEven(n);
}

Nếu hàm IsEven() trả về true tức là n là số chẵn và ngược lại trả về false thì n là số lẻ.

Giả sử chúng ta truyền vào n = 5 thì cơ chế hoạt động của nó như hình dưới đây:

* Lưu ý: Nếu các bạn đã học qua khóa học C++ căn bản thì chắc chắn các bạn đã biết được toán tử NOT (!). Đây là một toán tử đảo ngược trạng thái logic. Nếu điều kiện toán hạng là true thì phủ định nó sẽ là false.

Dựa vào đó ta có !!!!!true = false. Như vậy kết quả trả về là false.

Các bạn có thể luyện tập bằng cách chạy code bằng tay với các tham số n khác. Đây là một trong những cách luyên tập giúp các bạn rèn luyện tư duy logic rất tốt.

Code mẫu:

#include <iostream>
using namespace std;

bool isEven(int n);
bool isOdd(int n);

bool isEven(int n){
  if(n == 0)
    return true;
  else 
    return isOdd(n - 1);
}

bool isOdd(int n){
  return !isEven(n);
}
int main() {
  int n = 5;
  bool kq = isEven(n);
  if(kq == true)
    cout<<n<<" là số chẵn";
  else  
    cout<<n<<" là số lẻ";

  cout<<"
---------------------------
";
  cout<<"Chương trình này được đăng tại Zaidap.com.net";
}

Kết quả:

3. Kết luận

Như vậy chúng ta đã tìm hiểu xong về đệ quy tương hỗ, đây là một hàm đệ quy được sử dụng nhiều trong các bài toàn phức tạp. Các bạn hãy luyện tập thật nhiều để thành thạo nó nhé. Đây cũng là bài cuối cùng trong series thuật toán đệ quy. Chúc các bạn học thật tốt nhé !!!