Trong C# là một thực hành tốt để sử dụng các hàm đệ quy trong các thuật toán?

Question

Trong nhiều ngôn ngữ chức năng sử dụng đệ quy được coi là một thực hành tốt. Tôi nghĩ rằng nó là tốt vì cách trình biên dịch tối ưu hóa mã ngôn ngữ chức năng.

Nhưng thực hành tốt có nên sử dụng đệ quy trong C# khi tạo thuật toán không? Có đúng khi nói về C#, thuật toán đệ quy sẽ dẫn đến chồng của bạn tăng lên đáng kể (nếu số lượng cuộc gọi là rất lớn) và điều này sẽ không nhanh chút nào và có thể dẫn đến tràn ngăn xếp. Hoặc cũng có một số tối ưu hóa xảy ra để làm cho chức năng đệ quy hiệu quả?

Tôi sẽ đánh giá cao nếu bạn đưa ra một số so sánh (tốc độ, bộ nhớ, khả năng đọc) giữa các thuật toán sử dụng đệ quy trong các ngôn ngữ hàm và C#.

Answer 1

Tuy nhiên, không sử dụng đệ quy sẽ khiến bạn viết lại thuật toán bằng cách sử dụng "Ngăn xếp" của riêng bạn, điều này cuối cùng sẽ phải tuân theo các điều kiện tương tự trong khi thực thi.

Bạn có thể tùy chỉnh kích thước ngăn xếp dựa trên nhu cầu của thuật toán, nhưng nếu bạn nhìn vào WPF/Silverlight và thuật toán liên quan đến giao diện người dùng bình thường, tất cả đều là đệ quy trong tự nhiên và mọi nhấp chuột, mỗi lần nhấn phím và mọi thông báo phương pháp đệ quy.

Check-out Creating Thread with Custom Stack Size,

Mặc dù tốc độ có thể thay đổi tùy thuộc vào các thuật toán và tính phức tạp, nhưng việc tạo ra thuật toán riêng không đệ quy sẽ làm cho công việc phức tạp hơn khi bạn sẽ được thực hiện tất cả các hoạt động lưu trữ dữ liệu của mình sử dụng danh sách, ngăn xếp Điều này là khá thiết kế vs vấn đề hiệu suất, nếu bạn muốn hiệu suất tốt hơn, sau đó thuật toán không đệ quy của bạn sẽ thực thi nhanh hơn, nhưng nó sẽ mất nhiều thời gian để thiết kế và thực hiện thuật toán như vậy. Trường hợp khác nếu bạn muốn có một giải pháp nhanh hơn thì bạn có thể viết thuật toán đệ quy sẽ chậm hơn trong thực thi nhưng nếu sự khác biệt chỉ là vài mili giây hoặc micro giây thì nó không đáng làm.

Answer 2

Vòng lặp luôn vượt trội hơn việc đệ quy vì ngăn xếp luôn có nhiều chi phí hơn trạng thái của bạn. Rất nhiều hoạt động luồng rất nhiều đi bộ ngăn xếp để bạn có được sự suy giảm hơn nữa. Tuy nhiên, khả năng đọc là một điểm cộng lớn vì vậy tôi sẽ sử dụng đệ quy trừ khi tôi cần mọi giọt nước hoa như trong các hoạt động xử lý hình ảnh hoặc tôi mong đợi ngăn xếp của tôi phát triển rất lớn - mặc dù tràn bộ nhớ gần như độc quyền do lỗi.

Answer 3

Ở đây, bài đăng này Recursive iterator performance giải thích sự khác biệt giữa phiên bản đệ quy và thao tác không đệ quy một cách chi tiết. Kết quả thật thú vị. Hãy xem

Answer 4

Trong triển khai hiện tại của Microsoft về trình biên dịch C#, tối ưu hóa cuộc gọi đuôi không được thực hiện. Điều này làm cho các thuật toán chức năng mà recurse sâu tràn ngăn xếp. Mặc dù tôi không khuyên bạn nên sử dụng các thuật toán đệ quy sâu trong C#, nhưng các phương thức không recurse sâu sắc sẽ không gây ra bất kỳ vấn đề gì.

Answer 5

Khi bạn cần đệ quy, bạn cần nó, ví dụ như đi bộ trên cây đầu tiên, hoặc phân tích đệ quy gốc.

Nếu bạn có lựa chọn, như sử dụng đệ quy thay vì vòng lặp, thì có thể đó là chức năng của ngôn ngữ bạn đang sử dụng. Hãy đơn giản.

Answer 6

Lý do đệ quy trong các ngôn ngữ chức năng là thực hành tốt không phải vì tối ưu đệ quy đuôi; đó là thực hành tốt vì đó là một cách đơn giản, mạnh mẽ để thể hiện rất nhiều thuật toán. Tối ưu hóa chỉ là gravy, và dù sao đuôi cuộc gọi tối ưu hóa không liên quan đến tất cả các hàm đệ quy. Vì vậy, với điều đó trong tâm trí, nó thực sự tuyệt vời để xây dựng các phương pháp đệ quy trong C#, nếu đó là cách tự nhiên nhất để thể hiện thuật toán của bạn. Rõ ràng, nếu nó quay ra có vấn đề về độ sâu ngăn xếp, nó có thể có ý nghĩa để làm cho nó lặp đi lặp lại. Nhưng để có một thuật toán đệ quy tự nhiên và làm cho nó lặp đi lặp lại mà không biết nó là một vấn đề tối ưu hóa sớm, và có thể làm cho mã của bạn không cần thiết phức tạp và khó đọc để đổi lấy hiệu năng ít.