Liên kết đệ quy là gì

Đệ quy là một phần quan trọng của lập trình hàm có thể giúp giải quyết các vấn đề phức tạp với các giải pháp tinh tế. Tuy nhiên, điều quan trọng là phải hiểu những ưu và khuyết điểm để có thể thực hiện chính xác.

LIÊN QUAN: Đệ quy trong lập trình là gì và bạn sử dụng nó như thế nào?

Đệ quy là gì?

Câu trả lời ngắn gọn là đệ quy về cơ bản là khi một hàm gọi chính nó, thường là với một số đầu vào khác được chuyển cho hàm bên dưới. Nó tự gọi đi gọi lại cho đến khi đáp ứng được điều kiện thoát, sau đó chuyển các kết quả trở lại ngăn xếp cuộc gọi, có khả năng thay đổi chúng theo hướng đi lên.

Câu trả lời dài là đệ quy có thể giúp giải quyết các vấn đề phức tạp bằng cách chia nhỏ chúng thành các tập con nhỏ hơn của bài toán chính. Bạn thường có cấu trúc dữ liệu với dữ liệu lồng nhau. Việc chia nhỏ dữ liệu này thành các lượng dữ liệu nhỏ hơn sẽ giúp xử lý dễ dàng hơn.

Ví dụ: giả sử rằng mỗi lá trong cây có một giá trị được liên kết với nó và chúng tôi muốn tìm tổng của tất cả các giá trị. Chúng ta có thể làm điều đó với một hàm như sau, đi qua từng lá cây, kiểm tra tất cả các con và tính tổng.

int CountAllLeaves(Leaf currentLeaf)
{
   // Start with the current value
   int Total = currentLeaf.value;
   // Add any children to the value, if any
   foreach(Leaf childLeaf in currentLeaf.children) 
   {
       Total = Total + CountAllLeaves(childLeaf);
   }
   return Total;
}

Điều này hoạt động vì CountAllLeaves không quan tâm bạn gọi nó bằng trang tính nào. Nó tự gọi mình liên tục cho đến khi chạm vào chiếc lá cuối cùng trên cây không có con. Do đó, nó chỉ đơn giản là trả về giá trị của chính nó. Giá trị đó được chuyển đến trang tính mẹ, giá trị này sẽ thêm giá trị của trẻ vào giá trị của chính nó, và sau đó được lặp lại cho tất cả các anh chị em mà trang tính con có. Cuối cùng, kết quả cuối cùng của hàm là tổng của tất cả các lá trong cây.

Tại một số thời điểm bạn phải trường hợp ngừng hoạt động, đó là một phần của vấn đề mà bạn biết câu trả lời mà không cần thực hiện thêm các cuộc gọi đệ quy. Nếu không, hàm sẽ lặp lại mãi mãi, khiến chương trình bị lỗi. Trong trường hợp này, trường hợp tạm dừng là khi hàm đến một lá không có con nào.

Nó không nhất thiết phải nói về cấu trúc dữ liệu lồng nhau như cây. Bạn có thể viết các hàm đệ quy xung quanh bất kỳ loại vấn đề nào. Ví dụ, để tính giai thừa của một số, bạn phải nhân nó với mọi số nhỏ hơn. Bạn có thể làm điều này rất dễ dàng với đệ quy:

int Factorial(int n)
{
   if (n <= 1)
       return 1;
 
   return n * Factorial(n-1);
}

Trong ví dụ này, trường hợp tạm dừng là khi n đạt đến 1, nơi cuối cùng nó trả về một giá trị và ngăn xếp cuộc gọi có thể được thu gọn.

Hãy xem một ví dụ trong thế giới thực. Trong đoạn mã này có một Container lớp chứa nhiều phần tử giao diện người dùng được liên kết với nó, cũng như nhiều vùng chứa con với các phần tử riêng của chúng. Nó sẽ được “kết xuất” thành một danh sách phẳng các phần tử có thể được hiển thị trên màn hình.

Đây thực sự là một cấu trúc dữ liệu cây khác, vì vậy cách tiếp cận cũng tương tự. Ngoại trừ trường hợp này, biến tổng là một danh sách, trong đó danh sách phần tử của mỗi vùng chứa được thêm vào.

Điều kỳ diệu của việc thực hiện đệ quy là nó bảo toàn thứ tự Z của các phần tử. Các phần tử được vẽ sau các phần tử khác xuất hiện ở trên cùng, vì vậy vùng chứa cho phần tử nhỏ nhất luôn xuất hiện ở trên cùng. Trong trường hợp này, tôi cũng thấy hữu ích khi hiển thị các phần tử lớp phủ, các phần tử này được thêm vào sau khi các phần tử khác và phần tử con đã hoàn thành kết xuất.

Sự nguy hiểm của đệ quy

Vì vậy, khi nào bạn nên sử dụng đệ quy trong mã của mình? Câu trả lời là bạn có thể nên tránh nó trong hầu hết các tình huống, đặc biệt là khi một giải pháp lặp lại với một vòng lặp đơn giản sẽ hoàn thành công việc.

Mỗi khi bạn gọi một hàm, chương trình của bạn sẽ phân bổ tài nguyên cho hàm đó. Tất cả các biến cục bộ và thông tin sẽ được chuyển đến ngăn xếp, đây là cấu trúc dữ liệu Cuối cùng vào, Đầu ra (LIFO). Điều này có nghĩa là lệnh gọi hàm cuối cùng luôn bị xóa đầu tiên, giống như một nhóm nơi bạn luôn xóa phần tử trên cùng.

Vấn đề với đệ quy là nó có thể sử dụng một lệnh gọi hàm lồng nhau cho bất kỳ phần tử nào đang được xử lý. Điều này dẫn đến chi phí cao hơn nhiều, vì mỗi lệnh gọi hàm cần một tập hợp các biến và tham số cục bộ của riêng nó. Cần thêm thời gian xử lý so với cách tiếp cận dựa trên vòng lặp.

Vòng lặp không có vấn đề này. Sau mỗi lần lặp lại vòng lặp, phần tử trên cùng của ngăn xếp sẽ bị xóa. Nó có thể xử lý một tỷ phần tử với cùng một ngăn xếp.

Sử dụng quá nhiều tài nguyên với các lệnh gọi hàm đệ quy có thể dẫn đến: tràn ngăn xếp, nơi chương trình có thể gặp sự cố dựa trên quá nhiều lệnh gọi lồng nhau. Điều này có thể xảy ra với các tập dữ liệu đặc biệt lớn hoặc với các thuật toán xấu như nhị phân hoặc đệ quy hàm mũ, các thuật toán này tự gọi chúng nhiều lần cho mỗi lần gọi hàm.

Sử dụng đệ quy một cách tiết kiệm

Đệ quy là tốt để có cho một số vấn đề nhất định, nhưng về cơ bản không có giải pháp đệ quy nào cho các vấn đề cũng không thể giải quyết bằng các vòng lặp (ngoại trừ đệ quy lồng nhau như hàm của Ackerman). Ngay cả các cấu trúc dữ liệu cây phức tạp cũng có thể được duyệt qua bằng cách sử dụng các vòng lặp và ngăn xếp. Nếu bạn cần xử lý một lượng lớn dữ liệu hoặc quá coi trọng hiệu suất, tốt hơn hết là bạn nên sử dụng giải pháp lặp lại.

Một vấn đề khác với đệ quy là nó có thể dẫn đến mã mà người khác khó hiểu, bởi vì nó thường mất một chút suy nghĩ trước khi ai đó hiểu được. Mặc dù nó thường có vẻ là giải pháp “thanh lịch” hơn, nhưng công việc của bạn với tư cách là một lập trình viên không phải để khoe khoang mà là viết mã chức năng, có thể đọc được.

Dù bằng cách nào, bạn sẽ muốn nghĩ xem liệu vấn đề được đề cập có tốt hơn là sử dụng vòng lặp hay không. Đệ quy nên là phương sách cuối cùng của bạn cho các vấn đề sẽ phức tạp hơn nhiều nếu không có nó. Trên thực tế, trong toàn bộ 40.000 dòng mã nguồn của tôi, tôi chỉ có một ví dụ về đệ quy cho bài viết này.

Và sau một giây nhìn vào nó, tôi thực sự nhận thấy một vấn đề. Trong khi nó hoạt động tốt, nó được viết theo cách lười biếng, rõ ràng và như vậy sử dụng nhiều bộ nhớ hơn mức cần thiết. Đây thực sự không phải là vấn đề với các cấu trúc dữ liệu nhỏ mà nó xử lý, nhưng nó đã tạo ra một new List() cho mỗi lần gọi hàm, và thêm vào kết quả của các phần tử con. Điều này có nghĩa là nếu nó có một vùng chứa với các con lồng nhau sâu sắc, nó sẽ tiếp tục lưu trữ cùng một dữ liệu mà không có lý do gì.

Giải pháp trong trường hợp này là chuyển hàm đệ quy một tham chiếu đến một danh sách bên ngoài và nối trực tiếp tất cả các phần tử vào đó. Điều này cũng có nghĩa là Render() chức năng trong một chức năng xử lý thiết lập cấp cao nhất cho chức năng xây dựng đệ quy.

Điều này đạt được cùng một giải pháp chính xác bằng cách thêm từng phần tử theo đúng thứ tự, nhưng giải quyết được vấn đề sử dụng bộ nhớ tăng theo cấp số nhân với mỗi cuộc gọi.

Tuy nhiên, tôi hài lòng với tính năng này vì nó khá ngắn gọn và hoàn thành công việc một cách dễ dàng. Nếu tôi chuyển đổi điều này thành một giải pháp sử dụng vòng lặp, nó sẽ phức tạp hơn rất nhiều và thực hiện điều tương tự. Bạn nên cân nhắc ưu và nhược điểm của việc sử dụng giải pháp đệ quy và chỉ sử dụng nó khi bạn không mong đợi việc sử dụng tài nguyên nghiêm trọng. Trong trường hợp này, tôi không mong đợi sẽ gọi hàm này với các vùng chứa lồng nhau có độ sâu hàng trăm phần tử, vì vậy bạn có thể sử dụng đệ quy ở đây.