<p>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!</p>
<p>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.</p>
<p>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ả.</p>
<p>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.</p>
<p>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ả.</p>
<p>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.</p>

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

<p style="text-align: justify;">Trong c&aacute;c b&agrave;i trước, ch&uacute;ng ta đ&atilde; nhắc lại kh&aacute; chi tiết về đệ quy v&agrave; l&agrave;m việc với một số v&iacute; dụ rất điển h&igrave;nh về việc sử dụng đệ quy trong c&aacute;c b&agrave;i to&aacute;n thực tế. Tuy nhi&ecirc;n, tr&ecirc;n thực tế c&oacute; nhiều c&aacute;ch triển khai đệ quy kh&aacute;c nhau. Trong b&agrave;i n&agrave;y, ch&uacute;ng ta sẽ t&igrave;m hiểu bốn dạng kh&aacute;c nhau của đệ quy: Đệ quy trực tiếp, đệ quy gi&aacute;n tiếp, đệ quy đu&ocirc;i v&agrave; đệ quy đầu.</p>
<h2 style="text-align: justify;">Đệ quy trực tiếp</h2>
<p style="text-align: justify;">Một h&agrave;m được gọi l&agrave; đệ quy trực tiếp nếu n&oacute; gọi đến ch&iacute;nh n&oacute; một c&aacute;ch lặp đi lặp lại trong nội dung th&acirc;n của h&agrave;m. Dạng đệ quy n&agrave;y phổ biến nhất, v&agrave; ta cũng đ&atilde; thấy ở c&aacute;c b&agrave;i trước. Dưới đ&acirc;y l&agrave; một v&iacute; dụ về đệ quy trực tiếp:</p>
<pre class="language-cpp"><code>int func(int n){
  func(n-1);  //Gọi đệ quy
}</code></pre>
<p style="text-align: justify;">Trong chương tr&igrave;nh n&agrave;y, bạn c&oacute; một h&agrave;m t&ecirc;n l&agrave; <code>func</code> gọi đến ch&iacute;nh n&oacute; trong phần th&acirc;n của h&agrave;m. Do đ&oacute;, bạn c&oacute; thể gọi n&oacute; l&agrave; đệ quy trực tiếp.</p>
<p style="text-align: justify;"><strong>V&iacute; dụ 1: </strong></p>
<p style="text-align: justify;">Đoạn chương tr&igrave;nh C++ sau sẽ t&iacute;nh gi&aacute; trị b&igrave;nh phương của một gi&aacute; trị đầu v&agrave;o <code>x</code> bằng phương ph&aacute;p đệ quy:</p>
<div class="code-editor__wrapped code-editor__edit__wrapped" style="text-align: justify;">
<table class="code-editor__table">
<tbody>
<tr class="code-editor__edit__row__first">
<td colspan="2">RUN_CODE (*** ph&acirc;n biệt ***)</td>
</tr>
<tr>
<td>C++</td>
<td>
<pre class="language-cpp" data-content="#include &lt;iostream&gt;
using namespace std;

// recursive function to calculate square of a number
int square(int x)
 {
  // base case
    if (x == 0)
    {
      return x; 
    }

  // recursive case
  else 
   {
      return square(x-1) + (2*x) - 1;
   }
}
int main() {
  // implementation of square function
  int input=10;
  cout &lt;&lt; input&lt;&lt;" data-language="cpp" data-ace-language="c_cpp" data-name-language="C++" data-main-file="main.cpp"><code>#include &lt;iostream&gt;
using namespace std;

// recursive function to calculate square of a number
int square(int x)
 {
  // base case
    if (x == 0)
    {
      return x; 
    }

  // recursive case
  else 
   {
      return square(x-1) + (2*x) - 1;
   }
}
int main() {
  // implementation of square function
  int input=10;
  cout &lt;&lt; input&lt;&lt;"^2 = "&lt;&lt;square(input);
  return 0;
}</code></pre>
</td>
</tr>
</tbody>
</table>
</div>
<p style="text-align: justify;">[___NOTE_V&iacute; dụ tr&ecirc;n hơi "Cồng kềnh" phải kh&ocirc;ng? Tuy nhi&ecirc;n ch&uacute;ng ta sẽ lấy n&oacute; như một v&iacute; dụ kh&aacute; funny về đệ quy._NOTE___]</p>
<h2 style="text-align: justify;">Đệ quy gi&aacute;n tiếp</h2>
<p style="text-align: justify;">Dạng đệ quy trong đ&oacute; h&agrave;m gọi ch&iacute;nh n&oacute; th&ocirc;ng qua việc gọi một h&agrave;m kh&aacute;c chứa n&oacute; được gọi l&agrave; đệ quy gi&aacute;n tiếp. Một chương tr&igrave;nh đệ quy gi&aacute;n tiếp c&oacute; cấu tr&uacute;c cơ bản như sau:</p>
<pre class="language-cpp"><code>int func1(int z)
{
  // some code...
  func2(z-1);
  // some code...
}

int func2(int y)
{
  // some code...
  func1(y-2);
  // some code...
}</code></pre>
<p style="text-align: justify;">Trong dạng n&agrave;y, ta c&oacute; thể thấy h&agrave;m <code>func1</code> gọi đến h&agrave;m <code>func2</code>, v&agrave; đến lượt m&igrave;nh h&agrave;m <code>func2</code> lại gọi lại h&agrave;m <code>func1</code>. Do đ&oacute;, ta thường gọi dạng n&agrave;y l&agrave; đệ quy gi&aacute;n tiếp.</p>
<p style="text-align: justify;"><strong>V&iacute; dụ 2:</strong></p>
<p style="text-align: justify;">Đoạn chương tr&igrave;nh C++ sau in ra c&aacute;c gi&aacute; trị từ <code>0</code> đến <code>20</code> sử dụng phương ph&aacute;p đệ quy gi&aacute;n tiếp. V&agrave; tất nhi&ecirc;n n&oacute; cũng hơi "cồng kềnh".</p>
<div class="code-editor__wrapped code-editor__edit__wrapped" style="text-align: justify;">
<table class="code-editor__table">
<tbody>
<tr class="code-editor__edit__row__first">
<td colspan="2">RUN_CODE (*** ph&acirc;n biệt ***)</td>
</tr>
<tr>
<td>C++</td>
<td>
<pre class="language-cpp" data-content="#include &lt;iostream&gt;
using namespace std;
int n=0;
// declaring functions
void func1(void);
void func2(void);

// defining recursive functions
void func1() 
{ 
  if (n &lt;= 20) 
  { 
    cout&lt;&lt;n&lt;&lt;" data-language="cpp" data-ace-language="c_cpp" data-name-language="C++" data-main-file="main.cpp"><code>#include &lt;iostream&gt;
using namespace std;
int n=0;
// declaring functions
void func1(void);
void func2(void);

// defining recursive functions
void func1() 
{ 
  if (n &lt;= 20) 
  { 
    cout&lt;&lt;n&lt;&lt;" ";  // prints n
    n++;           // increments n by 1
    func2();       // calls func2() 
  } 
  else
    return; 
} 

void func2() 
{ 
  if (n &lt;= 20) 
  { 
    cout&lt;&lt;n&lt;&lt;" ";  // prints n
    n++;           // increments n by 1
    func1();       // calls func1()
  } 
  else
    return; 
} 

// Driver Program 
int main(void) 
{ 
  func1(); 
  return 0; 
} </code></pre>
</td>
</tr>
</tbody>
</table>
</div>
<h2 style="text-align: justify;">Đệ quy đu&ocirc;i</h2>
<p style="text-align: justify;">Một h&agrave;m đệ quy được gọi l&agrave; đệ quy đu&ocirc;i nếu như lời gọi đệ quy l&agrave; h&agrave;m được gọi cuối c&ugrave;ng được thực hiện trong th&acirc;n h&agrave;m đệ quy. Dưới đ&acirc;y l&agrave; cấu tr&uacute;c của một h&agrave;m đệ quy đu&ocirc;i:</p>
<pre class="language-cpp" data-content="int%20func(int%20z)%0A%7B%0A%C2%A0%C2%A0printf(%E2%80%9C%25d%E2%80%9D%2Cz)%3B%0A%C2%A0%C2%A0func(z-1)%3B%C2%A0%C2%A0%C2%A0%2F%2FL%E1%BB%9Di%20g%E1%BB%8Di%20%C4%91%E1%BB%87%20quy%20%C4%91%C6%B0%E1%BB%A3c%20th%E1%BB%B1c%20hi%E1%BB%87n%20%E1%BB%9F%20cu%E1%BB%91i%20c%C3%B9ng%20c%E1%BB%A7a%20h%C3%A0m.%0A%7D" data-language="cpp" data-ace-language="c_cpp" data-name-language="C++" data-main-file="main.cpp"><code>int func(int z)
{
  printf(&ldquo;%d&rdquo;,z);
  func(z-1);   //Lời gọi đệ quy được thực hiện ở cuối c&ugrave;ng của h&agrave;m.
}</code></pre>
<p style="text-align: justify;">Trong đoạn chương tr&igrave;nh tr&ecirc;n, bạn c&oacute; thể thấy rằng lời gọi đệ quy được thực thi sau c&aacute;c c&acirc;u lệnh kh&aacute;c. Điều n&agrave;y l&agrave;m cho chương tr&igrave;nh sẽ kh&ocirc;ng cần nhớ bất cứ trạng th&aacute;i g&igrave; trước đ&oacute;. Do đ&oacute;, dạng đệ quy n&agrave;y rất dễ d&agrave;ng để c&oacute; thể chuyển thể th&agrave;nh dạng c&agrave;i đặt sử dụng v&ograve;ng lặp.</p>
<h2>Đệ quy đầu</h2>
<p style="text-align: justify;">Một h&agrave;m được gọi l&agrave; đệ quy đầu nếu lời gọi đệ quy được thực hiện trước c&aacute;c thao t&aacute;c kh&aacute;c trong h&agrave;m. Sau khi trả lại, sẽ c&oacute; một c&aacute;i g&igrave; đ&oacute; cần đ&aacute;nh gi&aacute;. V&igrave; vậy, dạng đệ quy n&agrave;y về cơ bản kh&aacute; l&agrave; kh&oacute; khăn để chuyển thể th&agrave;nh dạng c&agrave;i đặt sử dụng v&ograve;ng lặp.</p>
<p style="text-align: justify;">X&eacute;t v&iacute; dụ sau:</p>
<pre class="language-c" data-content="int%20fun(int%20z)%0A%7B%0A%C2%A0%C2%A0fun(z-1)%3B%20%2F%2FL%E1%BB%9Di%20g%E1%BB%8Di%20%C4%91%E1%BB%87%20quy%20%C4%91%C6%B0%E1%BB%A3c%20th%E1%BB%B1c%20hi%E1%BB%87n%20tr%C6%B0%E1%BB%9Bc%0A%C2%A0%C2%A0printf(%E2%80%9C%25d%E2%80%9D%2Cz)%3B%0A%7D" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>int fun(int z)
{
  fun(z-1); //Lời gọi đệ quy được thực hiện trước
  printf(&ldquo;%d&rdquo;,z);
}</code></pre>
<p style="text-align: justify;">Trong h&agrave;m n&agrave;y, bạn c&oacute; thể thấy rằng c&oacute; c&aacute;c thao t&aacute;c kh&aacute;c cần được thực thi sau lời gọi đệ quy. Do đ&oacute;, chương tr&igrave;nh cần nhớ c&aacute;c trạng th&aacute;i trước đ&oacute; b&ecirc;n trong của khối lệnh n&agrave;y. Điều n&agrave;y g&acirc;y kh&oacute; khăn cho qu&aacute; tr&igrave;nh chuyển thể n&oacute; th&agrave;nh v&ograve;ng lặp.</p>
<p style="text-align: justify;">N&oacute;i chung, đệ quy đu&ocirc;i lu&ocirc;n tốt hơn. Mặc d&ugrave; cả hai đều c&oacute; c&ugrave;ng độ phức tạp về thời gian v&agrave; kh&ocirc;ng gian, nhưng c&aacute;c dạng đệ quy đu&ocirc;i c&oacute; lợi thế hơn về bộ nhớ trong ngăn xếp của h&agrave;m. C&aacute;c đệ quy đầu sẽ cần chờ đợi trong bộ nhớ ngăn xếp h&agrave;m cho đến khi c&aacute;c c&acirc;u lệnh đệ quy được thực thi ho&agrave;n tất. Điều n&agrave;y g&acirc;y ra độ trễ trong kết quả tổng thể, trong khi c&aacute;c đệ quy đu&ocirc;i sẽ dừng ngay trong ngăn xếp h&agrave;m khi thực thi.</p>
<p><img style="width: 600px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/5000990a-565e-40f1-9c70-619a11b11362" alt="C&aacute;c dạng đệ quy" /></p>
<p style="text-align: justify;">Một điều nữa đ&oacute; l&agrave; ch&uacute;ng ta sẽ rất kh&oacute; chuyển thể dạng đệ quy đầu sang c&aacute;c dạng sử dụng v&ograve;ng lặp để tăng tốc độ thực thi cũng như vượt qua hạn chế về kh&ocirc;ng gian bộ nhớ được cho ph&eacute;p bởi đệ quy bởi c&aacute;c tr&igrave;nh bi&ecirc;n dịch v&agrave; hệ điều h&agrave;nh. Tr&ecirc;n thực tế đệ quy trực tiếp v&agrave; đệ quy đu&ocirc;i l&agrave; hai dạng phổ biến nhất thường gặp.</p>
<p style="text-align: justify;">Tiếp theo, ch&uacute;ng ta h&atilde;y tiếp tục thực h&agrave;nh với một số b&agrave;i tập để th&agrave;nh thạo c&aacute;c dạng đệ quy n&agrave;y.</p>