Đệ quy tương hỗ (Mutual 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 tương hỗ (Mutual Recursion) trong C / C++. Đây là hàm đệ quy cuối cùng mà mình giới thiệu đến các bạn, ở các bài viết trước mình đã giới thiệu qua 5 hàm đệ quy trong C / C++.

Chúng ta sẽ cùng nhau tìm hiểu về hàm đệ quy tương hỗ (Mutual Recursion) là gì? Cơ chế hoạt động của nó, cùng với đó là ví dụ sử dụng nó trong C / C++.

Hàm đệ quy tương hỗ (Mutual Recursion) trong C / C++ là gì?

Ví dụ: Mình có hàm A() gọi đệ quy hàm B(), mà bên trong hàm B() lại gọi đệ quy hàm A().

int A();
int B();
int A(){
   B();
}
int B(){
   A();'
}

Ví dụ: Mình có hàm đệ quy tương hỗ dùng để kiểm tra số chẵn hay số lẻ.

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

Ta có hai hàm đó là IsEven() dùng để kiểm tra số chẵn và hàm IsOld() để kiểm tra số lẻ. Hai hàm này gọi qua lại với nhau, như vậy được xem là hàm đệ quy tương hỗ.

Cơ chế hoạt động của hàm đệ quy tương hỗ (Mutual Recursion) trong C / C++

Mình sẽ sử dụng ví dụ ở phần một để thực hiện cơ chế hoạt động của hàm đệ quy tương hỗ (Mutual Recursion) trong C / C++.

Thật ra đối với bài toán kiểm tra số chãn lẻ không cần sử dụng đến đệ quy, tuy nhiên vì đây là bài toán cơ bản, nên các bạn sẽ dễ hình dung hơn.

Số chẵn là số khi chúng ta chia hết cho 2 (2n) và số lẻ là số chia cho 2 dư 1 (2n - 1).

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

Hàm IsEven() sẽ trả về true nếu là số chẵn và trả về false nếu là số lẻ. Bây giờ mình giả sử truyền vào số n = 5. Khi đó hàm đệ quy tương hỗ sẽ hoạt động như dưới đây.

Như hình trên, chúng ta lần lượt gọi đệ quy hàm IsEven(), sau đó lại gọi hàm đệ quy IsOld(), cứ như vậy cho đến khi n == 0. Đây là điều kiện dừng của hàm đệ quy. kết quả cuối cùng trả về là !!!!!true = false.

*Lưu ý: Toán tử NOT (!) là một toán tử đảo ngược trạng thái, ví dụ đang là true thì !true sẽ bằng fasle.

Dựa vào hàm đệ quy tương hỗ trên, mình sẽ thực hiện chương trình kiểm tra số chẵn lẻ trong C / C++. Chương trình này sẽ được viết bằng hai ngôn ngữ khác nhau là C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>
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)
    printf("%d là số chẵn",n);
  else 
    printf("%d là số lẻ",n);
 
  printf("\n---------------------------\n");
  printf("Chương trình này được đăng tại codehow.net");
}

Chương trình C++:

#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<<"\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ề hàm đệ quy tương hỗ (Mutual Recursion) trong C / C++. Các bạn cần nắm vững các kiến thức dưới đây của hàm đệ quy tương hỗ:

• Hàm đệ quy tương hỗ là hàm gọi đệ quy hàm khác, mà hàm này lại gọi đệ quy lại nó.
• Cơ chế hoạt động tuần tự theo các hàm đệ quy.

Đây cũng là hàm đệ quy cuối cùng mà mình muốn giới thiệu đến các bạn. Cảm ơn các bạn rất nhiều, hẹn gặp lại các bạn ở bài viết khác nhé !!!!