Chi tiết về đệ quy trong C++ – 4 bài tập đệ quy có lời giải chi tiết
Đệ 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, Isinhvien 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_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.
}
Để 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;
}
Giải thích thuật toá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
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.
Bài tập về đệ quy trong C++ (có đáp án chi tiết)
Dưới đây là các bài tập siêu kinh điển về đệ quy mà bạn không thể bỏ qua.
1. Tìm số Fibonacci bằng đệ quy
Dãy 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 hai phần tử trước nó.
Hàm tìm số fibonacci bằng đệ 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);
}
}
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 chung nhỏ nhất của 2 số là các khái niệm khá phổ biến trong toán học:
- Ước chung lớn nhất của 2 số: Là số lớn nhất mà 2 số đó cũng chia hết
- Bội chung nhỏ nhất của 2 số: Là số nhỏ nhất cùng chia hết cho 2 số đó
Hàm tìm ước chung lớn nhất và bội chung nhỏ nhất bằng đệ 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) / USCLN(a, b);
}
3. In đảo ngược một số nguyên dương n
Cho một số nguyên dương n, hãy viết hàm đệ quy để in ra màn hinh đảo ngược cúa số nguyên dương đấy.
Hàm in đảo ngược một số nguyên dương n:
void InDaoNguoc(int n)
{
if(n!=0)
{
cout<<n%10;
InDaoNguoc(n/10);
}
}
4. In ra dạng nhị phân của số nguyên dương n
Cho một số nguyên dương n, hãy viết hàm in ra dạng nhị phân của số nguyên dương đó
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);
cout<<n%2;
}
}
Hy vọng sau bài viết này sẽ 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 của Isinhvien hay và bổ ích thì hãy chia sẻ nó đến với bạn bè của mình để ủng hộ cho Isinhvien và giúp Isinhvien ngày càng phát triển hơn nhé! Chúc các bạn thành công!
