Có cách nào để biết trong C++ độ sâu đệ quy tối đa mà không gọi một cách rõ ràng đệ quy cho đến khi nó bị treo?Tìm chiều sâu đệ quy tối đa
Tôi đã thấy điều đó bị giới hạn bởi kích thước của ngăn xếp. Có lẽ nó có thể hữu ích để tìm thấy ở một mức độ đệ quy cụ thể số lượng không gian trống trong ngăn xếp. Có thể không?
Điều duy nhất mà tôi có thể nghĩ đến ngay bây giờ là sử dụng getrlimit để nhận kích thước tối đa của ngăn xếp dành riêng cho quy trình của bạn. Điều tiếp theo cần làm là tìm cách nhận kích thước ngăn xếp hiện đang được sử dụng. Tôi nghĩ rằng getrusage là con đường để đi nhưng sau khi nhìn vào man -page và một vài bài viết trên SO có vẻ như nó không còn hỗ trợ tính năng này đặc biệt. Vì vậy, bạn phải tìm một cách khác. Tôi tin rằng Valgrind cũng báo cáo việc sử dụng ngăn xếp để xem xét mã nguồn và tài liệu của nó có thể hữu ích.
Một khi bạn có thể để có được kích thước ngăn xếp hiện tại bạn có thể đo
trạng thái ban đầu của nó trước khi bạn bắt đầu đệ quy (để bạn có thể loại trừ này từ tính toán của bạn vì nó không liên quan gì đến làm với đệ quy thân)
thay đổi nó cho một sự lặp lại đơn
Loại trừ phân bổ chồng ban đầu cùng với USI ng tổng kích thước ngăn xếp và phân bổ cần thiết cho một bước đệ quy duy nhất bạn sẽ có thể ước tính số lượng các cuộc khảo sát bạn có thể có cho hệ thống nhất định. Tôi không chắc liệu nó có hoạt động hay không và thậm chí nếu số liệu chính xác là phụ thuộc nhiều vào hệ thống bạn đang sử dụng (sau khi tất cả ngăn xếp liên quan chặt chẽ đến số lượng bộ nhớ ảo mà quy trình có thể có).
Độ sâu đệ quy tối đa phụ thuộc vào lượng bộ nhớ được sử dụng bởi (các) hàm, dung lượng bộ nhớ trên nền tảng của bạn và giới hạn (nếu có) bởi hệ điều hành hoặc trình biên dịch.
Trong một cuộc gọi đệ quy, bộ nhớ bị chiếm đóng bởi:
Một hàm đệ quy không có tham số và không có các biến địa phương sẽ có một chiều sâu có thể cao hơn (số lượng cuộc gọi đệ quy) so với một chức năng mà qua rất nhiều đối tượng lớn và chiếm một nhiều biến cục bộ. Vì vậy, câu trả lời cho câu hỏi của bạn là: số lượng tối đa các cuộc gọi đệ quy phụ thuộc vào lượng bộ nhớ bị chiếm bởi một cuộc gọi đệ quy, dung lượng bộ nhớ trên hệ thống và bất kỳ giới hạn nào được cài đặt bởi trình biên dịch hoặc hệ điều hành. Các hàm đệ quy khác nhau chiếm một lượng bộ nhớ khác nhau.
Nếu bạn biết tất cả các mục này, thì bạn có thể tính toán số lần truy cập tối đa có thể.
Không có gì trong 'C++' xác định độ sâu tối đa. Độ sâu tối đa phụ thuộc vào kiến trúc CPU, chi tiết triển khai trình biên dịch cụ thể và hàm thực sự được đệ quy (cùng với các hàm con mà nó gọi).Giống như bất kỳ vấn đề khác, chắc chắn, nếu bạn biết tất cả các thông số bạn có thể xác định một giải pháp .... nhưng trong trường hợp này nó có thể dễ dàng hơn nhiều để chỉ cần thực hiện cuộc gọi rõ ràng và xem những gì bạn nhận được. – mah
Mặc dù có một đoạn trong '[temp.inst]' cho biết có một số thực hiện được xác định. – NathanOliver
Vì vậy, nếu có một cách để kiểm tra kích thước ngăn xếp miễn phí để ngăn chặn đệ quy khi nó dưới một giới hạn quy định? – Jepessen