Đệ quy trong C++ là một phương pháp cực kỳ quan trọng và là nền tảng của nhiều thuật toán. Vì vậy, hiểu về đệ quy sẽ giúp bạn dễ dàng tiếp cận và có thêm nhiều kiến thức về lập trình. Trong bài viết này chúng tôi sẽ chia sẻ với các bạn mọi thứ về đệ quy cũng như các bài tập đệ quy kèm theo lời giải chi tiết để các bạn hiểu rõ hơn nhé!
Đệ quy là gì?
Đệ quy trong C++ là quá trình trong đó một phương thức được gọi lặp đi lặp lại. Một hàm trong C++ tự gọi lại chính nó được gọi là phương thức đệ quy. Một hàm đệ quy sẽ bao gồm điều kiện dừng và lệnh gọi hàm đệ quy, cú pháp cụ thể như sau:
Return_type Tên hàm (Tham số) { Stop_condition; trả về Tên hàm(new_parameter); // hoặc một biểu thức chứa lệnh gọi hàm. }
Để giúp bạn hình dung dễ dàng hơn, đây là một ví dụ về hàm đệ quy cho phép bạn tính giai thừa của một số tự nhiên :
dài dài Giaithua(int n) { if (n==0 || n==1) return 1; ngược lại trả về Giaithua(n-1) * n; }
Giải thích thuật toán : Ở đây điều kiện dừng là n=0 hoặc n=1, sẽ trả về giá trị 1 (Thực hiện 0!=1!=1). Ngược lại, nếu n>1 thì hàm sẽ trả về n*Giaithua(n-1). Ví dụ: nếu chúng ta cho n lấy giá trị 3, chương trình sẽ thực hiện như sau:
GiaiTha(3) GiaiTha(2) GiaiTha(1) trả về 1 trả về 2*1 = 2 trả về 3*2 = 6
Do đó, mục đích của hàm đệ quy là chia bài toán thành các bài toán nhỏ hơn cho đến khi đạt được điều kiện cơ bản. Một lưu ý quan trọng khi sử dụng đệ quy là cần có điều kiện dừng. Nếu không, hàm sẽ được gọi liên tục không dừng và chương trình sẽ không thể kết thúc.
Đệ quy trực tiếp và đệ quy gián tiếp trong C++
Đệ quy có hai 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ì 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 đó gọi lại hàm kia thì gọi là đệ quy gián tiếp.
Trong số đó, đệ quy trực tiếp phổ biến hơn đệ quy gián tiếp.
Bài tập đệ quy C++ (có đáp án chi tiết)
Dưới đây là một số bài tập siêu kinh điển về đệ quy mà bạn không thể bỏ qua.
Tìm số Fibonacci bằng đệ quy
Dãy số Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1, các phần tử sau được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng của hai phần tử đứng trước.
Hàm tìm số Fibonacci đệ quy
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 đệ quy
Ước chung lớn nhất và bội số chung nhỏ nhất của hai số là những khái niệm khá phổ biến trong toán học:
- Ước chung lớn nhất của hai số : là số lớn nhất chia hết cho hai số đó
- Bội chung nhỏ nhất của hai số: số nhỏ nhất chia hết cho hai số
Hàm tìm ước chung lớn nhất và bội chung nhỏ nhất theo cách đệ quy:
//Tìm ước chung lớn nhất int UCLN(int a, int b) { if (b == 0) return a; trả về UCLN(b, a % b); } //Tìm bội số chung nhỏ nhất int BCNN(int a, int b) { return (a * b) / USCLN(a, b); }
In đảo ngược một số nguyên dương n
Cho một số nguyên dương n, viết hàm đệ quy in ra nghịch đảo của số nguyên dương này.
Hàm đảo ngược số nguyên dương n:
void InDaoNguyen(int n) { if(n!=0) { cost<<n%10; InDaoNguc(n/10); } }
In ra dạng nhị phân của số nguyên dương n
Cho số nguyên dương n, viết hàm in ra dạng nhị phân của số nguyên dương này
Hàm in ra dạng nhị phân của số nguyên dương n
void NhiPhan(int n) { if(n!=0) { NhiPhan (n/2); chi phí<<n%2; } }
Hi vọng bài viết này giúp các bạn hiểu rõ hơn về đệ quy trong C++ ! Nếu thấy bài viết này hay và hữu ích, hãy chia sẻ tới bạn bè để ủng hộ nhé! Chúc may mắn!
