Đệ quy nhị phân (Binary 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 nhị phân (Binary Recursion) trong C / C++. Đây là một hàm đệ quy được sử dụng khá nhiều trong quá trình xử lý việc sắp xếp, tìm kiếm, ... .

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

Hàm đệ quy nhị phân (Binary Recursion) trong C / C++ là gì?

Ví dụ: Mình có hàm tìm dãy số Fibonanci là hàm đệ quy nhị phân.

int fib(int n){
if(n <= 2) return 1; // điểm dừng
return fib(n - 1) + fib(n - 2);
} 

Như các bạn đã thấy thì hàm fib() gọi lại hai lần chính nó trong thân hàm.

Tương tự như vậy bất kì hàm nào có câu lệnh gọi lại hai lần chính nó trong thân hàm thì được xem là hàm đệ quy nhị phân.

Để hiểu rõ hơn, chúng ta hãy qua phần thứu hai là phần cơ chế hoạt động của hàm đệ quy nhị phân nhé.

Cơ chế hoạt động của hàm đệ quy nhị phân (Binary Recursion) trong C / C++

Hàm đệ quy nhị phân (Binary Recursion) hoạt động dựa trên hai cơ chế là Stack và cấu trúc cây. Thông thường chúng ta thường sử dụng cách biểu diễn dưới dạng cây để biểu diễn đệ quy nhị phân. Vì vậy trong phần này mình sẽ sử dụng cấu trúc cây để biểu diễn hàm đệ quy nhị phân nhé.

Chúng ta sẽ thực hiện ví dụ tìm số Fibonanci thứ n, với n là một số nguyên dương được nhập bởi người dùng.

Trước tiên chúng ta cần tìm hiểu số Fibonanci là gì để nắm được thuật toán của nó.

Dãy số Fibonanci là một dãy vô hạn các số tứ nhiên tuân theo quy luật phần tử sau bằng tổng hai phần tử trước đó. Dãy Fibonanci bắt đầu bằng hai số là 0 và 1.

Công thức:

Hàm fib():

int fib(int n){
  if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Bây giờ giả sử chúng ta cần tìm số Fibonanci thứ 6 nghĩa là fib(6), khi đó cơ chế hoạt động của hàm đệ quy nhịn phân fib() được biểu diễn dưới dạng cây như sau:

Điểm dừng của hàm đệ quy trên là n <= 2. Nghĩa là nếu n <= 2 thì trả về 1. Nó cứ gọi đệ quy cho đến khi gặp điểm dừng, khi đó kết quả là 8, đây là số Fibonanci thứ 6 trong dãy.

Tương tự như vậy cho các số Fibonanci khác trong dãy, các bạn có thể tự luyện tập bằng cách giải tay như mình vậy nhé.

Ví dụ sử dụng hàm đệ quy nhị phân (Binary Recursion) trong C / C++

Trong phần này mình sẽ thực hiện hai ví dụ sử dụng hàm đệ quy nhị phân (Binary Recursion) trong C / C++. Mỗi chương trình mình đều viết bằng hai ngôn ngức khác nhau, các bạn có thể tham khảo nhé.

Ví dụ 1: Viết chương trình tìm số Fibonanci thứ n, với n được nhập bởi người dùng.

Chương trình C:

#include <stdio.h>

int fib(int n){
  if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}
 
int main(void) {
  int kq,n;
  printf("Nhập vị trí n muốn tìm trong dãy fibonacci: ");
  scanf("%d", &n);
  kq = fib(n);
  printf("\nSố fibonacci ở vị trí %d là: %d",n,kq);

  printf("\n---------------------------------\n");
  printf("Chương trình này được đăng tại codehow.net");
  return 0;  
}

Chương trình C++:

#include <iostream>
using namespace std;
 
int fib(int n){
  if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}
 
int main() {
  int kq,n;
  cout<<"Nhập vị trí n muốn tìm trong dãy fibonacci: ";
  cin>>n;
  kq = fib(n);
  cout<<"\nSố fibonacci ở vị trí "<<n<<" là: "<<kq;
  cout<<"\n-----------------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Ví dụ 2: Viết chương trình in dãy số Fibonanci thứ n, với n được nhập bởi người dùng.

Chương trình C:

#include <stdio.h>

int fibonacci_series(int);

int main(void) {
  int count, c = 0, i;
   printf("Nhập vào số lượng các số trong chuỗi Fibonacci: ");
   scanf("%d", &count);
   printf("\n chuỗi Fibonacci là: \n");
   for ( i = 1 ; i <= count ; i++ )
   {
      printf("%d\n", fibonacci_series(c));
      c++; 
   }

  printf("\n---------------------------------\n");
  printf("Chương trình này được đăng tại codehow.net");
  return 0;  
}

int fibonacci_series(int num)
{
   if ( num == 0 )
     return 0;
   else if ( num == 1 )
     return 1;
   else
     return ( fibonacci_series(num-1) + fibonacci_series(num-2) );
}

Chương trình C++:

#include <iostream>
using namespace std;
int fibonacci_series(int);
int main()
{
   int count, c = 0, i;
   cout<<"Nhập vào số lượng các số trong chuỗi Fibonacci: ";
   cin>>count;
   cout<<"\n chuỗi Fibonacci là: \n";
   for ( i = 1 ; i <= count ; i++ )
   {
      cout<<fibonacci_series(c)<<endl;
      c++; 
   }
   cout<<"\n----------------------------\n";
   cout<<"Chương trình này được đăng tại codehow.net";
}
int fibonacci_series(int num)
{
   if ( num == 0 )
     return 0;
   else if ( num == 1 )
     return 1;
   else
     return ( fibonacci_series(num-1) + fibonacci_series(num-2) );
}

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 nhị phân (Binary Recursion) trong C / C++. Qua bài này, các bạn cần nắm vững các kiến thức đưới đây:

• Hàm đệ quy nhị phân là hàm gọi đệ quy chính nó hai lần trong thân hàm.
• Có hai cách biểu diễn cơ chế hoạt động của hàm đệ quy là cấu trúc Stack và cấu trúc cây.
• Ví dụ dãy Fibonanci sử dụng hàm đệ quy nhị phân.

Ở bài tiếp theo mình sẽ giới thiệu đến các bạn hàm đệ quy đa tuyến trong C / C++. Các bạn nhớ chú ý theo dõi nhé, cảm ơn các bạn rất nhiều !!!