Làm cách nào để theo dõi độ sâu đệ quy?

Question

Tôi có chức năng đệ quy mà tôi đang khắc phục sự cố. Tôi muốn xuất độ sâu đệ quy ... tức là. bao nhiêu lần hàm gọi chính nó.

Nếu tôi sử dụng biến tĩnh tăng ở đầu hàm và giảm ở cuối.

Điều này có chính xác cung cấp cho tôi mức độ sâu không?

recurse() 
    { 
    static int depth = 0; 
    depth++; 
    /* 
    do stuff 
    recurse() 
    */ 
    depth--; 
    return return_value; 
    } 

Answer 1

recurse(int depth = 0){ 
    .... 
    recurse(depth+1); 
} 

Answer 2

Trong một bối cảnh luồng duy nhất nó sẽ làm việc.

Answer 3

có, nó sẽ hoạt động. tôi không thấy bất kỳ vấn đề gì với điều đó.

Answer 4

Không, có thể không, nếu ngoại lệ được ném. Một lựa chọn tốt hơn (và phổ biến hơn) là:

int recurse(int depth=0) 
{ 
    recurse(depth+1) 
    return return_value; 
} 

Answer 5

Để làm cho nó dễ dàng hơn và

• ngoại lệ an toàn hơn
• chủ đề an toàn hơn
• hỗ trợ tree recursion

(!)

_{Nếu bạn thực sự kéo trí tưởng tượng của bạn, điều này có thể làm cho trình biên dịch dễ dàng hơn trong một số cuộc gọi đệ quy, và/hoặc thực hiện tối ưu hóa cuộc gọi đuôi trong trường hợp đệ quy đuôi. Tôi không có bằng chứng rằng điều này đóng một vai trò, nhưng tôi có thể tưởng tượng tham chiếu các biểu tượng bên ngoài từ bên trong một cơ quan chức năng ảnh hưởng đến tối ưu hóa trình biên dịch.}

Tôi đề nghị:

stuff recurse(int level=0) 
{ 

    //... 
    recurse(level+1); 

    //... (return stuff?) 
    //... (throw exceptions?) 

    //... 
    recurse(level+1); 

    //... (return stuff?) 

} 

Answer 6

Nếu bạn muốn làm phi intrusively bạn thực sự có thể yêu cầu trình biên dịch của bạn để công cụ mỗi cuộc gọi này cho bạn, ví dụ với gcc:

#include <iostream> 
static __thread int depth=-1; 
extern "C" { 
    void __cyg_profile_func_enter (void *, void *) __attribute__((no_instrument_function)); 
    void __cyg_profile_func_exit (void *, void *) __attribute__((no_instrument_function)); 
    void __cyg_profile_func_enter (void *func, void *caller) 
    { 
     depth++; 
    } 


    void __cyg_profile_func_exit (void *func, void *caller) 
    { 
     depth--; 
    } 
} 

class Foo { 
public: 
    void bar() { 
     std::cout << "bar: " << depth << std::endl; 
    } 
}; 

int main() { 
    Foo f; 
    f.bar(); 
    return 0; 
} 

Bạn sẽ cần phải biên dịch với -finstrument-functions để làm việc này.

Answer 7

Bạn thường muốn tăng biến sâu được xác định bên ngoài hàm đệ quy cho mục đích an toàn luồng và in từ bên ngoài chức năng đó.

Dưới đây là một ví dụ đơn giản thừa chứng minh điều đó:

#include <stdio.h> 

unsigned factorial(unsigned x, unsigned* depth) 
{ 
    if (x <= 1) 
    return 1; 

    ++*depth; 

    return x * factorial(x - 1, depth); 
} 

int main(void) 
{ 
    unsigned depth, f; 

    depth = 0; f = factorial(1, &depth); 
    printf("factorial=%u, depth=%u\n", f, depth); 

    depth = 0; f = factorial(2, &depth); 
    printf("factorial=%u, depth=%u\n", f, depth); 

    depth = 0; f = factorial(6, &depth); 
    printf("factorial=%u, depth=%u\n", f, depth); 

    return 0; 
} 

Output:

C:\>recdep.exe 
factorial=1, depth=0 
factorial=2, depth=1 
factorial=720, depth=5