Làm cách nào để tìm độ sâu của hàm đệ quy trong C++

Question

Làm thế nào tôi có thể tìm độ sâu hiện tại bên trong một hàm đệ quy trong C++ mà không vượt qua ở cấp độ trước? tức là có thể biết bao nhiêu lần hàm được gọi mà không sử dụng tham số để theo dõi mức và chuyển số đó thành tham số mỗi lần hàm được gọi?

Ví dụ hàm đệ quy của tôi trông như thế này:

DoSomething(int level) 
{ 
    print level; 
    if (level > 10) 
    return; 
    DoSomething(++level); 
} 

main 
{ 
    DoSomething(0); 
} 

Answer 1

Dựa trên câu trả lời đã do JoshD:

void recursive() 
{ 
    static int calls = 0; 
    static int max_calls = 0; 
    calls++; 
    if (calls > max_calls) 
     max_calls = calls; 

    recursive(); 

    calls--; 
} 

này reset bộ đếm sau khi chức năng đệ quy là xong, nhưng vẫn theo dõi độ sâu tối đa của đệ quy.

Tôi sẽ không sử dụng các biến tĩnh như thế này cho bất kỳ điều gì ngoài thử nghiệm nhanh, sẽ bị xóa ngay sau đó. Nếu bạn thực sự cần phải theo dõi điều này trên cơ sở liên tục có những phương pháp tốt hơn.

Answer 2

Bạn có thể sử dụng một biến tĩnh địa phương, nếu bạn không quan tâm đến thread-an toàn.

Mặc dù, điều này sẽ chỉ cung cấp cho bạn số lượng thích hợp trong lần đầu tiên bạn chạy quy trình đệ quy của mình. Một kỹ thuật tốt hơn sẽ là một lớp bảo vệ kiểu RAII có chứa một biến tĩnh bên trong. Khi bắt đầu quy trình đệ quy, hãy xây dựng lớp bảo vệ. Các nhà xây dựng sẽ tăng biến tĩnh nội bộ, và destructor sẽ decrement nó. Bằng cách này, khi bạn tạo một khung ngăn xếp mới, bộ đếm tăng thêm một, và khi bạn quay trở lại từ mỗi khung ngăn xếp, bộ đếm sẽ giảm đi một.

struct recursion_guard 
{ 
    recursion_guard() { ++counter; } 

    ~recursion_guard() { --counter; } 

    static int counter; 
}; 

int recursion_guard::counter = 0; 

void recurse(int x) 
{ 
    recursion_guard rg; 
    if (x > 10) return; 
    recurse(x + 1); 
} 

int main() 
{ 
    recurse(0); 
    recurse(0); 
} 

Lưu ý rằng điều này vẫn không an toàn chỉ. Nếu bạn cần an toàn luồng, bạn có thể thay thế biến lưu trữ tĩnh bằng biến luồng-cục bộ lưu trữ, hoặc sử dụng boost::thread_specific_ptr hoặc các tiện ích cục bộ của C++ 0x.

Answer 3

Bạn có thể sử dụng một biến tĩnh trong hàm ...

void recursive() 
{ 
static int calls = 0; 
calls++; 
recursive(); 
} 

Tất nhiên, điều này sẽ tiếp tục đếm khi bạn bắt đầu cuộc gọi có nguồn gốc mới ....

Answer 4

chuyển đổi level thành biến mẫu của đối tượng mới (thường là mẫu) có khả năng chứa đối số và (có thể) hàm. sau đó bạn có thể tái sử dụng giao diện ắc quy đệ quy.

Answer 5

Bạn cũng có thể thử sử dụng biến toàn cục để ghi nhật ký.

var depth = 0; 

DoSomething() 
{ 
    print ++depth; 
    if (depth > 10) 
    return; 
    DoSomething(); 
} 

main 
{ 
    DoSomething(0); 
} 

Answer 6

Bạn cũng có thể vượt qua cấp dưới dạng thông số mẫu, nếu có thể xác định tại thời điểm biên dịch. Bạn cũng có thể sử dụng một đối tượng hàm. Điều này là bởi xa và đi các lựa chọn tốt nhất - ít rắc rối, và các biến tĩnh nên tránh bất cứ nơi nào có thể.

struct DoSomething { 
    DoSomething() { 
     calls = 0; 
    } 
    void operator()() { 
     std::cout << calls; 
     calls++; 
     if (calls < 10) 
      return operator()(); 
     return; 
    } 
    int calls; 
}; 

int main() { 
    DoSomething()(); // note the double(). 
    std::cin.get(); 
} 

Answer 7

Nếu bạn muốn nó được re-entrant và thread-safe, tại sao không:

void rec(int &level) // reference to your level var 
{ 
    // do work 

    rec(++level); // go down one level 
} 

main() 
{ 
    //and you call it like 
    int level=0; 
    rec(level); 

    cout<<level<<" levels."<<endl; 
} 

Không tĩnh/biến toàn cục mess up luồng và bạn có thể sử dụng các biến khác nhau cho khác nhau chuỗi đệ quy cho các vấn đề tái nhập.