GIẢI THUẬT ĐỆ QUY
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Đệ quy tương hỗ (Mutual Recursion)

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

test php

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.

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:

Bài viết này được đăng tại [free tuts .net]

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:

co che de quy tuong ho PNG

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

Kết quả:

de quy tuong ho PNG

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

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