Sử dụng đệ quy trong C#

Question

Có quy tắc chung nào khi sử dụng đệ quy về cách tránh lưu lượng truy cập không?

Answer 1

Đã bao nhiêu lần bạn sẽ có thể recurse sẽ phụ thuộc vào:

• Ngăn xếp kích thước (mà thường là 1MB IIRC, nhưng nhị phân có thể được hiệu chỉnh bằng tay, tôi sẽ không khuyên bạn nên làm như vậy)
• Mức độ mỗi cấp độ của đệ quy sử dụng (một phương pháp có 10 biến không được kẹp Guid biến cục bộ sẽ có nhiều ngăn xếp hơn một phương pháp không có bất kỳ biến cục bộ nào),
• JIT bạn đang sử dụng - đôi khi JIT sẽ sử dụng tính năng đệ quy đuôi, các thời điểm khác sẽ không . Các quy tắc rất phức tạp và tôi không thể nhớ chúng. (Có một blog post by David Broman back from 2007 và an MSDN page from the same author/date, nhưng chúng có thể đã lỗi thời.)

Làm thế nào để tránh tràn ngăn xếp? Đừng chấp nhận quá xa :) Nếu bạn không thể chắc chắn rằng sự đệ quy của bạn sẽ chấm dứt mà không đi rất xa (tôi sẽ lo lắng "hơn 10" mặc dù điều đó rất an toàn) sau đó viết lại nó để tránh đệ quy.

Answer 2

Ngoài việc có kích thước ngăn xếp hợp lý và đảm bảo bạn chia và chinh phục sự cố của mình sao cho bạn liên tục làm việc trên một vấn đề nhỏ hơn, không thực sự.

Answer 3

Tôi không biết bất kỳ bộ cứng nào để tránh lưu lượng truy cập stackoverflows. Cá nhân tôi cố gắng đảm bảo -
1. Tôi có các trường hợp cơ bản của mình.
2. Mã đạt đến trường hợp cơ bản tại một số điểm.

Answer 4

Nếu bạn đang tìm kiếm chính mình tạo ra nhiều khung ngăn xếp, bạn có thể muốn xem xét việc hủy bỏ đệ quy của bạn thành một vòng lặp.

Đặc biệt nếu bạn đang thực hiện nhiều cấp đệ quy (A-> B-> C-> A-> B ...), bạn có thể thấy rằng bạn có thể trích xuất một trong các cấp đó thành vòng lặp và tiết kiệm cho mình một số bộ nhớ .

Answer 5

Giới hạn bình thường, nếu không còn nhiều thứ trong ngăn xếp giữa các cuộc gọi kế tiếp, sẽ có khoảng 15000-25000 cấp độ sâu. 25% số đó nếu bạn đang sử dụng IIS 6+.

Hầu hết các thuật toán đệ quy có thể được biểu diễn lặp lại.

Có nhiều cách khác nhau để tăng không gian ngăn xếp được phân bổ, nhưng thay vào đó tôi sẽ cho phép bạn tìm phiên bản lặp lại trước tiên. :)

Answer 6

Nó thực sự phụ thuộc vào thuật toán đệ quy bạn đang sử dụng. Nếu đó là đệ quy đơn giản, bạn có thể làm một cái gì đó như thế này:

public int CalculateSomethingRecursively(int someNumber) 
{ 
    return doSomethingRecursively(someNumber, 0); 
} 

private int doSomethingRecursively(int someNumber, int level) 
{ 
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber)) 
     return someNumber; 
    return doSomethingRecursively(someNumber, level + 1); 
} 

Cần lưu ý rằng cách tiếp cận này thực sự hữu ích khi mức đệ quy có thể được định nghĩa là giới hạn hợp lý. Trong trường hợp điều này không thể xảy ra (chẳng hạn như thuật toán phân chia và chinh phục), bạn sẽ phải quyết định cách bạn muốn cân bằng sự đơn giản so với hiệu suất so với giới hạn tài nguyên. Trong những trường hợp này, bạn có thể phải chuyển đổi giữa các phương thức khi bạn đạt đến giới hạn được xác định trước. Một phương tiện hiệu quả để làm điều này mà tôi đã sử dụng trong thuật toán quicksort là để làm điều đó như một tỷ lệ của tổng kích thước của danh sách. Trong trường hợp này, giới hạn logic là kết quả của khi điều kiện không còn tối ưu.

Answer 7

Tôi chỉ nghĩ đến việc đệ quy đuôi, nhưng hóa ra là C# không hỗ trợ nó. Tuy nhiên, Net-Khung dường như để hỗ trợ nó:

http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

Answer 8

Hãy nhớ rằng, nếu bạn phải tự hỏi về giới hạn hệ thống, sau đó bạn có lẽ làm điều gì đó sai lầm khủng khiếp.

Vì vậy, nếu bạn nghĩ rằng bạn có thể bị tràn ngăn xếp trong hoạt động bình thường thì bạn cần nghĩ đến một cách tiếp cận khác cho vấn đề.

Không khó để chuyển đổi hàm đệ quy thành hàm lặp lại, đặc biệt khi C# có bộ sưu tập Generic :: Stack. Sử dụng loại Stack di chuyển bộ nhớ được sử dụng vào heap của chương trình thay vì ngăn xếp. Điều này cung cấp cho bạn phạm vi địa chỉ đầy đủ để lưu trữ dữ liệu đệ quy. Nếu đó là không đủ, nó không quá khó để trang dữ liệu vào đĩa. Nhưng tôi nghiêm túc xem xét các giải pháp khác nếu bạn đến giai đoạn này.

Answer 9

Kích thước ngăn xếp mặc định cho chuỗi là 1 MB, nếu bạn đang chạy theo CLR mặc định. Tuy nhiên, các máy chủ khác có thể thay đổi điều đó. Ví dụ, máy chủ ASP thay đổi mặc định là 256 KB. Điều này có nghĩa rằng bạn có thể có mã chạy hoàn toàn tốt theo VS, nhưng bị phá vỡ khi bạn triển khai nó vào môi trường lưu trữ thực.

May mắn thay bạn có thể chỉ định kích thước ngăn xếp, khi bạn tạo một chuỗi mới bằng cách sử dụng hàm tạo chính xác. Theo kinh nghiệm của tôi hiếm khi cần thiết, nhưng tôi đã thấy một trường hợp mà đây là giải pháp.

Bạn có thể chỉnh sửa tiêu đề PE của chính tệp nhị phân để thay đổi kích thước mặc định. Điều này rất hữu ích nếu bạn muốn thay đổi kích thước cho chuỗi chính. Nếu không, tôi sẽ khuyên bạn nên sử dụng các nhà xây dựng thích hợp khi tạo chủ đề.

Answer 10

Tôi đã viết một bài viết ngắn về điều này here. Về cơ bản, tôi vượt qua một tham số tùy chọn được gọi là, chiều sâu, thêm 1 cho nó mỗi khi tôi đi sâu hơn vào nó. Trong phương pháp đệ quy, tôi kiểm tra độ sâu cho một giá trị. Nếu nó lớn hơn giá trị tôi đặt, tôi ném một ngoại lệ. Giá trị (ngưỡng) sẽ phụ thuộc vào nhu cầu ứng dụng của bạn.