Lý thuyết đệ quy

Đệ quy trong C++ 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. 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. Trong bài viết ngày này, vncode.tech sẽ chia sẻ với các bạn tất tần tật mọi thứ về đệ quy cùng với các bài tập đệ quy có lời giải chi tiết để giúp bạn hiểu rõ hơn về nó nữa đấy!

Đệ quy là gì?

Đệ quy trong C++ 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 trong C++ 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 cụ thể như sau:

Kiểu_dữ_liệu   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.
}

Để giúp bạn dễ hình dung hơn thì dưới đây sẽ là ví dụ về hàm đệ quy giúp tính giai thừa của một số tự nhiê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à hoặc là thì sẽ trả về giá trị là . Ngược lại, nếu , hàm sẽ trả về . Chẳng hạn ta cho nhận giá trị là , 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 

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.

Đệ quy trực tiếp và đệ quy gián tiếp trong C++

Đệ quy có 2 loại: đệ quy trực tiếp và đệ quy gián tiếp

• Đệ 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.

Trong đó, đệ quy trực tiếp phổ biến hơn so với đệ quy gián tiếp.