Phương thức Đệ quy trong C++

Đệ quy là một phương thức vô cùng quan trọng và là cơ sở của rất rất nhiều thuật toán trong lập trình. Vì vậy, hiểu được đệ quy sẽ giúp bạn dễ dàng tiếp cận và học hỏi thêm nhiều kiến thức khác về lập trình.

Đệ quy là gì?

Đệ quy là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một hàm gọi lại chính nó được gọi là phương thức đệ quy. Trong một hàm đệ quy sẽ gồm có điều kiện dừng và lời gọi hàm đệ quy, cú pháp:

Kiểu_trả_về   Tên_hàm (Các_tham_số)
{ 
    Điều_kiện_dừng;
    return Tên_hàm (Các_tham_số_mới) ;
    // hoặc một biểu thức có chứa lời gọi hàm.
}

Ví dụ về hàm Đệ quy tính giai thừa của một số nguyên:

long long Giaithua(int n)
{
    if (n==0 || n==1)
       return 1;
    else
       return Giaithua(n-1) * n;
}

Ở đây, điều kiện dừng chính là n=0 hoặc là n=1 thì sẽ trả về giá trị là 1 ( Do 0!=1!=1). Ngược lại, nếu n>1, hàm sẽ trả về n*Giaithua(n-1). Chẳng hạn ta cho n nhận giá trị là 3, chương trình sẽ thực thi như sau:

GiaiThua(3) 
GiaiThua(2) 
GiaiThua(1) 
return 1 
return 2*1 = 2 
return 3*2 = 6

Như vây, mục đích của hàm đệ quy là chia vấn đề thành các vấn đề nhỏ hơn cho đến khi đạt được điều kiện cơ bản.

Lưu ý quan trọng khi sử dụng đệ quy là bắt buộc phải có điều kiện dừng, nếu không có thì sẽ làm hàm gọi hàm liên tục không có điểm dừng và dẫn đến chương trình không thể kết thúc được.

Các kiểu hàm đệ quy:

Đệ quy trực tiếp: Khi một hàm gọi chính nó thì được gọi là đệ quy trực tiếp, ví dụ ở trên là một ví dụ điển hình của đệ quy trực tiếp
Đệ quy gián tiếp: Khi một hàm gọi hàm khác và hàm đó lại gọi lại hàm kia, thì đây được gọi là đệ quy gián tiếp.

Thông thường thì chúng ta sử dụng đệ quy trực tiếp.

Một số bài toán sử dụng đệ quy:

Hàm tìm dãy số Fibonacci:

int fibonacci(int n)
{
    if (n < 0) {
        return -1;
    }
    else if (n == 0 || n == 1) {
        return n;
    }
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Tìm Ước chung lớn nhất và Bội chung nhỏ nhất bằng phương thức đệ quy:

//Tìm ước chung lớn nhất
int UCLN(int a, int b) {
    if (b == 0)
        return a;
    return UCLN(b, a % b);
}
//Tìm bội chung nhỏ nhất
int BCNN(int a, int b) {
    return (a * b) / UCLN(a, b);
}

In đảo ngược một số nguyên dương:

void InDaoNguoc(int n)
{
    if(n != 0)
    {
     cout<<n % 10;
     InDaoNguoc(n/10);
    }
}

In ra dạng nhị phân của một số nguyên dương:

void NhiPhan(int n) {
      if(n != 0) {
             NhiPhan (n/2);
             cout << n % 2;
        }
}

Trên đây là một số chia sẻ về vấn đề sử dụng phương thức xử lý đệ quy trong các bài toán lập trình. Ở đây chúng ta đi sâu và nghiên cứu về ngôn ngữ C++. Hy vọng sẽ giúp cho các bạn hiểu rõ hơn về phương thức này./.

Lập trình C/C++

Phương thức Đệ quy trong C++

Đệ quy là gì?

Một số bài toán sử dụng đệ quy:

Trả lời Hủy