Đệ quy trong C++ (Recursion)

Khóa học lập trình C++ căn bản

5.0 (2 đánh giá)
Tạo bởi DG Cập nhật lần cuối 22:40 10-08-2019 2.336 lượt xem 0 bình luận
Học nhanh

Danh sách bài học

Đệ quy trong C++ (Recursion)

Dẫn nhập

Ở bài học trước, Kteam đã chia sẻ cho các bạn về CON TRỎ HÀM TRONG C++. Đó là những kiến thức khá quan trọng mà bạn cần nắm trong C++.

Hôm nay, chúng ta sẽ cùng tìm hiểu về Đệ quy trong C++ (Recursion).


Nội dung

Để đọc hiểu bài này tốt nhất các bạn nên có kiến thức cơ bản về:

Trong bài ta sẽ cùng tìm hiểu các vấn đề:

  • Đệ quy là gì?
  • Điều kiện dừng (điều kiện cơ sở)
  • Một số bài toán đệ quy kinh điển
  • Đệ quy so với vòng lặp

Đệ quy là gì?

Trong lập trình, một hàm được gọi là đệ quy nếu bên trong thân hàm có một lời gọi đến chính nó.

Hàm đệ quy luôn có điều kiện dừng được gọi là “điểm neo”. Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa.

Khi được gọi, hàm đệ quy thường được truyền cho một tham số, thường là kích thước của bài toán lớn ban đầu. Sau mỗi lời gọi đệ quy, tham số sẽ nhỏ dần, nhằm phản ánh bài toán đã nhỏ hơn và đơn giản hơn. Khi tham số đạt tới một giá trị cực tiểu (tại điểm neo), hàm sẽ chấm dứt.

Ví dụ:

#include <iostream>
using namespace std;

void countDown(int count)
{
	cout << "push " << count << '\n';
	countDown(count - 1); // countDown() tự gọi lại chính nó
}

int main()
{
	countDown(3);

	return 0;
}

Output:

Khi countDown(3) được gọi, thì "push 3" được in ra và countDown(2) được gọi. Sau đó countDown(2) in "push 2" và gọi countDown(1). Sau đó countDown(1) in "push 1" và gọi countDown(0). Theo trình tự, trong hàm countDown(n) sẽ gọi countDown(n-1), việc này được lặp lại vô hạn, đây là một hàm đệ quy lặp vô hạn.

Trong bài HÀM NỘI TUYẾN TRONG C++ (Inline functions), bạn đã biết khi một hàm được gọi, nó sẽ được đưa vào ngăn xếp (stack), hàm đệ quy cũng vậy, mỗi lần gọi chính nó thì nó lại được đưa vào ngăn xếp (stack), nếu như không có điểm dừng, hoặc gọi mãi mà chưa tới điểm dừng, sẽ dễ xảy ra tình trạng tràn bộ nhớ ngăn xếp (stack).


Điều kiện dừng (điều kiện cơ sở)

Hàm đệ quy phải có một điều kiện kết thúc đệ quy, nếu không chương trình sẽ lặp vô hạn (đến khi tràn bộ nhớ ngăn xếp). Điều kiện dừng của hàm đệ quy gọi là điều kiện cơ sở.

Ví dụ:

#include <iostream>
using namespace std;

void countDown(int count)
{
	cout << "push " << count << '\n';

	if (count > 1) // điều kiện dừng
		countDown(count - 1);

	cout << "pop " << count << '\n';
}

int main()
{
	countDown(3);
	return 0;
}

Output:

Trong chương trình trên, do có điều kiện kết thúc (count > 1), nên trong hàm countDown(1) không gọi countDown(0), vì vậy "pop 1" được in ra và kết thúc hàm countDown(1). Lúc này, hàm countDown(1) bật ra khỏi ngăn xếp, hàm countDown(2) tiếp tục thực thi tại vị trí sau lời gọi hàm countDown(1), do đó "pop 2" được in ra. Tuần tự đến khi thoát ra toàn bộ các lời gọi hàm đệ quy.


Một số bài toán đệ quy kinh điển

Bài toán tính giai thừa

Cho n là một số tự nhiên (n>=0). Hãy tính giai thừa của n (n!) biết rằng 0! = 1 và n! = (n-1)! * n.

Phân tích:

Theo giả thiết, ta có : n! = (n-1)! * n. Như vậy :

  • Để tính n! ta cần phải tính (n-1)!
  • Để tính (n-1)! ta phải tính (n-2)!

Cứ như vậy, cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có được kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác.

long GiaiThua(int n)
{
	if (n == 0)
	{
		return 1; // điều kiện dừng
	}

	return n * GiaiThua(n - 1); // gọi đệ quy
}

Dãy Fibonaci

Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau :

  • F(n) = 0, nếu n = 0
  • F(n) = 1, nếu n = 1
  • F(n) = F(n-1) + F(n-2), nếu n > 1

Yêu cầu: tính số fibonaci thứ n với n cho trước.

#include <iostream>
using namespace std;

int fibonacci(int number)
{
	if (number == 0)
		return 0; // điều kiện dừng
	if (number == 1)
		return 1; // điều kiện dừng
	return fibonacci(number - 1) + fibonacci(number - 2);
}

int main()
{
	// in dãy 15 số fibonacci
	for (int count = 0; count < 15; ++count)
		cout << fibonacci(count) << " ";

	return 0;
}

Output: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377


Đệ quy so với vòng lặp

Một câu hỏi thường gặp là: "Tại sao lại sử dụng hàm đệ quy trong khi bạn có thể thực hiện với vòng lăp (vòng lặp for hoặc while )?".

Thông thường, các bài toán đệ quy có thể giải quyết bằng vòng lặp. Tuy nhiên, hàm đệ quy giúp code dễ đọc và đơn giản hơn.

Ví dụ: in dãy fibonaci

#include <iostream>
using namespace std;

int main()
{
	int n1 = 0;
	int n2 = 1;

	for (int i = 1; i <= 15; ++i)
	{
		cout << n1 << " ";

		int nextTerm = n1 + n2;
		n1 = n2;
		n2 = nextTerm;
	}

	return 0;
}

Output: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Sử dụng vòng lặp thường có hiệu suất cao hơn so với phiên bản hàm đệ quy. Vì khi một hàm được gọi, chương trình sẽ tốn một lượng chi phí cho việc đưa hàm vào ngăn xếp (stack).

Chú ý: Ưu tiên sử dụng vòng lặp thay vì đệ quy.


Kết luận

Qua bài học này, bạn đã nắm được khái niệm Đệ quy trong C++ (Recursion) và những bài toán cơ bản về đệ quy.

Trong bài tiếp theo, mình sẽ giới thiệu cho các bạn về  KHUÔN MẪU HÀM TRONG C++ (Function templates).

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.


Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả

DG
Founder, Designer, Developer at Kteam

Khóa học

Khóa học lập trình C++ căn bản

Hiện nay, C++ đã là cái tên rất quen thuộc trong ngành lập trình. Mặc dù C++ là ngôn ngữ lập trình đã ra đời khá lâu, nhưng không phải ai cũng có cơ hội để tìm hiểu về nó.

Vì vậy, Kteam đã xây dựng lên khóa học LẬP TRÌNH C++ CĂN BẢN để cung cấp một lượng kiến thức về ngôn ngữ C++ nói riêng, và các khái niệm khác trong lập trình nói chung.

Nội dung khóa học sẽ được phân tách một cách chi tiết, nhằm giúp các bạn dễ hiểu và thực hành được ngay. Serial dành cho những bạn chưa có bất kỳ kiến thức gì về lập trình, hoặc những bạn mất căn bản muốn lấy lại kiến thức nền tảng lập trình, cụ thể là C++.

Đánh giá

Phạm Tấn Thành Moderator đã đánh giá 11:19 19-08-2019

Làm sao để hiểu đệ quy nhanh ta

luan vo đã đánh giá 10:22 17-08-2019

Bài giảng rất dễ hiểu. Cảm ơn mn

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.