Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!
Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.
Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.
Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.
Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.
H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.

Cấu trúc dữ liệu và Giải thuật

Cho một đoạn chương tr&igrave;nh sử dụng phương ph&aacute;p đệ quy như dưới đ&acirc;y.
<div class="before" style="text-align: justify;">
<pre class="language-c" data-content="public%20void%20countDown(int%20n)%20%7B%0A%09if(n%20%3D%3D%200)%20return%3B%0A%09System.out.println(n%20%2B%20%22...%22)%3B%0A%09waitASecond()%3B%0A%09countDown(n-1)%3B%0A%7D%0A%09%09%09%09%0Apublic%20void%20countDown(int%20n)%20%7B%0A%09while(n%20%3E%200)%20%7B%0A%09%09System.out.println(n%20%2B%20%22...%22)%3B%0A%09%09waitASecond%20()%3B%0A%09%09n%20-%3D%201%3B%0A%09%7D" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>public void countDown(int n) {
	if(n == 0) return;
	System.out.println(n + "...");
	waitASecond();
	countDown(n-1);
}
				
public void countDown(int n) {
	while(n &gt; 0) {
		System.out.println(n + "...");
		waitASecond ();
		n -= 1;
	}</code></pre>
</div>
<div class="description" style="text-align: justify;">
Ta thấy n&oacute; tương đối kh&oacute; hiểu v&agrave; đặc biệt l&agrave; kh&oacute; debug để xem luồng thực thi của n&oacute; đ&uacute;ng kh&ocirc;ng?
[___QUESTION_H&atilde;y thay phương ph&aacute;p Đệ quy bằng V&ograve;ng lặp._QUESTION___]
<h2>Đặt vấn đề</h2>
Trước đ&acirc;y, t&ocirc;i c&oacute; nghe một bạn l&agrave;m manager phụ tr&aacute;ch tuyển dụng c&ocirc;ng nghệ của một c&ocirc;ng ty kh&aacute; c&oacute; tiếng n&oacute;i l&agrave;: "Kh&ocirc;ng bao giờ tuyển một lập tr&igrave;nh vi&ecirc;n t&iacute;nh giai thừa bằng đệ quy". Điều đ&oacute; c&oacute; l&iacute; do của n&oacute;. Đệ quy thường l&agrave; một phương &aacute;n được nghĩ đến ngay lập tức do t&iacute;nh tự nhi&ecirc;n của lời giải. Tuy nhi&ecirc;n việc sử dụng đệ quy v&ocirc; tội vạ d&ugrave; chưa c&acirc;n nhắc c&aacute;c phương &aacute;n thay thế kh&aacute;c l&agrave; một điều thật sự kinh khủng v&agrave; đ&aacute;ng tr&aacute;ch. Mặc d&ugrave; đ&uacute;ng l&agrave; giải ph&aacute;p đệ quy thường r&otilde; r&agrave;ng v&agrave; dễ nhận ra hơn phương ph&aacute;p lặp nhưng ch&uacute;ng ta n&ecirc;n cẩn thận để kh&ocirc;ng lạm dụng n&oacute;. Một giải ph&aacute;p đệ quy phức tạp v&agrave; kh&oacute; hiểu c&oacute; thể được coi l&agrave; một dấu hiệu kh&ocirc;ng tốt trong code v&agrave; n&ecirc;n được thay thế bằng phương ph&aacute;p lặp (thường kết hợp với một số kiểu T&aacute;i cấu tr&uacute;c code kh&aacute;c). C&aacute;c phương ph&aacute;p lặp thường hiệu quả hơn so với c&aacute;c giải ph&aacute;p đệ quy v&igrave; ch&uacute;ng kh&ocirc;ng g&acirc;y tốn k&eacute;m t&agrave;i nguy&ecirc;n trong việc gọi phương thức nhiều lần.
Ch&uacute;ng ta sử dụng Đệ quy khi cần thực hiện một t&aacute;c vụ phức tạp c&oacute; thể được chia th&agrave;nh c&aacute;c t&aacute;c vụ con. Đệ quy được thực hiện bằng c&aacute;ch một phương thức gọi ch&iacute;nh n&oacute; để giải quyết c&aacute;c t&aacute;c vụ con. Trong khi gọi đệ quy, gi&aacute; trị của c&aacute;c trường cục bộ của phương thức được đặt tr&ecirc;n ngăn xếp phương thức cho đến khi t&aacute;c vụ con được thực hiện bởi lệnh gọi đệ quy. Do đ&oacute;, mỗi khi phương thức đệ quy được gọi, c&aacute;c trường cục bộ được đặt tr&ecirc;n ngăn xếp của h&agrave;m v&agrave; được sử dụng lại sau khi lệnh gọi đệ quy ho&agrave;n th&agrave;nh. Phương ph&aacute;p tổng qu&aacute;t cho việc T&aacute;i cấu tr&uacute;c c&oacute; thể l&agrave; triển khai một Ngăn xếp &ldquo;m&ocirc; phỏng&rdquo; ngăn xếp của h&agrave;m, nơi m&agrave; c&aacute;c trường cục bộ c&oacute; thể được đặt v&agrave;o.
Đ&ocirc;i khi, giải ph&aacute;p đệ quy kh&ocirc;ng cần bảo to&agrave;n bất kỳ trường cục bộ n&agrave;o trong qu&aacute; tr&igrave;nh gọi đệ quy, điều n&agrave;y l&agrave;m cho việc t&aacute;i cấu tr&uacute;c trở n&ecirc;n dễ d&agrave;ng hơn nhiều. Trường hợp n&agrave;y được gọi l&agrave; đệ quy đu&ocirc;i (tail recursion). Đệ quy đu&ocirc;i thường được coi l&agrave; một c&aacute;ch l&agrave;m tệ v&agrave; n&ecirc;n được thay thế bằng v&ograve;ng lặp. 
<h2>Cơ chế giải đệ quy</h2>
Để thực hiện việc giải đệ quy th&agrave;nh v&ograve;ng lặp, ch&uacute;ng ta cần thực hiện:
<ul>
<li style="font-weight: 400;" aria-level="1">X&aacute;c định trường hợp cơ sở của đệ quy. Khi đạt đến trường hợp cơ sở, đệ quy sẽ kết th&uacute;c. Mỗi đệ quy phải c&oacute; một trường hợp cơ sở x&aacute;c định. Ngo&agrave;i ra, mỗi lệnh gọi đệ quy phải tiến tới trường hợp cơ sở (nếu kh&ocirc;ng, c&aacute;c lệnh gọi đệ quy sẽ được thực hiện v&ocirc; tận). Trong v&iacute; dụ tr&ecirc;n, trường hợp cơ sở l&agrave; <code>n == 0</code>.</li>
<li style="font-weight: 400;" aria-level="1">Triển khai một v&ograve;ng lặp lặp lại cho đến khi đạt đến trường hợp cơ sở.</li>
<li style="font-weight: 400;" aria-level="1">Thực hiện c&aacute;c thao t&aacute;c biến đổi biến lặp trong v&ograve;ng lặp để n&oacute; tiến tới trường hợp cơ sở. </li>
</ul>
<h2>V&iacute; dụ</h2>
Quay lại v&iacute; dụ tr&ecirc;n, ta c&oacute; thể thực hiện giải đệ quy v&agrave; t&aacute;i cấu tr&uacute;c đoạn m&atilde; sau: 
<pre class="language-java" data-content="public%20class%20CountDown%20%7B%0A%09public%20void%20countDown(int%20n)%20%7B%0A%09%09if(n%20%3D%3D%200)%20return%3B%0A%09%09System.out.println(n%20%2B%20%22...%22)%3B%0A%09%09waitASecond()%3B%0A%09%09countDown(n-1)%3B%0A%09%7D%0A%09public%20void%20waitASecond()%20%7B%0A%09%09try%20%7B%0A%09%09%09Thread.sleep(1000)%3B%0A%09%09%7D%0A%09%09catch%20(InterruptedException%20ignore)%20%7B%0A%09%09%7D%0A%09%7D%0A%09public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%09%09CountDown%20c%20%3D%20new%20CountDown()%3B%0A%09%09c.countDown(10)%3B%0A%09%7D%0A%7D" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>public class CountDown {
	public void countDown(int n) {
		if(n == 0) return;
		System.out.println(n + "...");
		waitASecond();
		countDown(n-1);
	}
	public void waitASecond() {
		try {
			Thread.sleep(1000);
		}
		catch (InterruptedException ignore) {
		}
	}
	public static void main(String[] args) {
		CountDown c = new CountDown();
		c.countDown(10);
	}
}</code></pre>
Sau khi cấu tr&uacute;c lại:
<pre class="language-java" data-content="public%20class%20CountDown%20%7B%0A%09public%20void%20countDown(int%20n)%20%7B%0A%09%09while(n%20%3E%200)%20%7B%0A%09%09%09System.out.println(n%20%2B%20%22...%22)%3B%0A%09%09%09waitASecond%20()%3B%0A%09%09%09n%20-%3D%201%3B%0A%09%09%7D%0A%09%7D%0A%09public%20void%20waitASecond()%20%7B%0A%09%09try%20%7B%0A%09%09%09Thread.sleep(1000)%3B%0A%09%09%7D%0A%09%09catch%20(InterruptedException%20ignore)%20%7B%0A%09%09%7D%0A%09%7D%0A%09public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%09%09CountDown%20c%20%3D%20new%20CountDown()%3B%0A%09%09c.countDown(10)%3B%0A%09%7D%0A%7D" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>public class CountDown {
	public void countDown(int n) {
		while(n &gt; 0) {
			System.out.println(n + "...");
			waitASecond ();
			n -= 1;
		}
	}
	public void waitASecond() {
		try {
			Thread.sleep(1000);
		}
		catch (InterruptedException ignore) {
		}
	}
	public static void main(String[] args) {
		CountDown c = new CountDown();
		c.countDown(10);
	}
}</code></pre>
</div>

Giải đệ quy bằng vòng lặp