Đệ quy và ứng dụng trong lập trình

Khi chúng ta bắt đầu thực hiện dự án lập trình thì sự “phồng lên” về kích thước của file chứa dữ liệu là điều không thể tránh khỏi. Nhằm mục đích tinh gọn và đơn giản dự án đi (đa phần dùng vòng lặp) thì Đệ Quy ra đời. Nó có ứng dụng cực kỳ to lớn trong lập trình.

Đệ quy, thực chất nó là gì?

Đơn giản là dùng những vấn đề nhỏ để giải quyết vấn đề lớn. Ví dụ như chúng ta có 1 vấn đề lớn và cách giải quyết vấn đề lớn này lại là kết quả của vấn đề nhỏ, vì vậy để giải quyết ta chia vấn đề lớn ra nhiều vấn đề nhỏ rồi bắt đầu giải quyết các vấn đề nhỏ hơn kế tiếp

Còn trong lập trình, định nghĩa đơn giản hơn là có một hàm tự gọi lại chính nó. Ví dụ như trong ngôn ngữ PHP:

<?php 
  // Chương trình tính tổng từ 1 -> n 
  function tinhTong($n) { 
    if ($n >0) { 
      return $n + tinhTong($n-1); 
    } 
    return $n; 
  } 
  // Ví dụ tinhTong(5) 
  // => 5 + tinhTong(4) => 5 + (4 + tinhTong(3)) => ... => 5 + (4 + (3 + (2 + 1))) = 15 
  // Bản quyền © 2020 bởi tienminhvy.com - Vui lòng ghi nguồn nếu chia sẻ lại! 
?>

Chương trình bên trên sẽ tính tổng các số từ 1 đến n. Ví dụ ta truyền 5 vào hàm (tinhTong(5)) thì kết quả trả về sẽ là 15. Cách thức hoạt động của hàm này như sau:

• Đầu tiên gọi hàm với giá trị truyền vào là 5: tinhTong(5)
• Sau đó, ngôn ngữ lập trình sẽ phân tích bằng cách thực thi hàm và ra kết quả là 5 + tinhTong(4)
• Tiếp tục như trên thì kết quả cuối cùng là 15. Ta thấy hàm tinhTong($n) tự thực hiện chính bản thân nó (gọi là tự gọi nó) nên hàm này được xem như là một hàm đệ quy

Thực chất, trong lập trình thường dùng nó để thay thế vòng lặp với số lần lặp chưa biết trước.

Lưu ý khi lập loại hàm đặc biệt này

Bạn phải tuân thủ theo các điều kiện:

• Viết câu lệnh điều kiện (if) sao cho hàm có thể tự thoát được, không gây tràn bộ nhớ
• Hàm thường phải có tham số truyền vào

Phân loại đệ quy

Hiện tại được chia làm 2 loại: đệ quy đầu (loại 1) và đệ quy đuôi (loại 2). Bên dưới đây là một ví dụ về đệ quy đuôi trong PHP:

<?php 
  // Ví dụ 
  // Chương trình sau có công dụng như chương trình trước 
  function tinhTong2($n, $tong=0) { 
    if ($n <= 0) { 
      return $tong; 
    } 
    return tinhTong2($n-1,$tong+$n); 
  } 
  // Ví dụ cho tinhTong2(5) 
  // => tinhTong2(5,0);  
  // => tinhTong2(4,5);  
  // => tinhTong2(3,9);  
  // => tinhTong2(2,12);
  // => tinhTong2(1,14);
  // => tinhTong2(0,15); => return 15 
  // Bản quyền © 2020 bởi tienminhvy.com - Vui lòng ghi nguồn nếu chia sẻ lại! 
?>

Cách thức hoạt động của nó cũng tương tự như đệ quy đầu ở ví dụ trên nhưng khác một tí là: chương trình sẽ thực hiện phép tính và lấy kết quả đó làm giá trị truyền vào cho hàm đệ quy lần 2 và chương trình chỉ thực hiện câu điều kiện 1 lần duy nhất.

Hiệu quả ở đây là sẽ làm giảm đáng kể sự lưu trữ (tạo vùng nhớ tạm thời để lưu trữ) và giảm việc thực hiện câu điều kiện. Nên có thể nói loại này giúp chương trình chạy nhanh hơn.

Phân biệt loại đệ quy

Ưu và nhược điểm

Ưu điểm

• Giúp chương trình nhẹ hơn, ít hơn
• Dễ đọc nếu thông thạo
• Trông ngầu hơn :v

Nhược điểm

• Dễ gặp rắc rối nếu bạn chưa nắm rõ bản chất của nó
• Dễ bị tràn bộ nhớ
• Cần chất xám nhiều hơn :v

Tóm lại

Các bạn thấy đệ quy rất hữu ích phải không nào, nhưng cũng phải lưu ý là không phải lúc nào chúng ta cũng nên dùng nó đâu nhé, chỉ nên dùng nếu thấy thực sự cần thiết mà thôi, nếu không rối não như chơi đấy @[email protected]

Tham khảo

• Một số ví dụ trong các ngôn ngữ lập trình khác
• Xem thêm: Khái niệm về hệ điều hành