如何跟蹤遞歸深度？

我有一個遞歸函數，我正在排除故障。我想輸出遞歸深度...即，函數自己調用多少次。如何跟蹤遞歸深度？

如果我使用一個靜態變量，該變量在函數頂部遞增並在底部遞減。

這會準確地給我深度級別嗎？

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

來源

2011-10-19 user1001776

試試看。（這顯然不是線程安全的，只是你知道。） –

經驗證據在這裏將是錯誤的。 –

感謝所有的答案...我將更新和發佈不久 – user1001776

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

來源

2011-10-19 23:13:25 romaninsh

在單線程情況下它會奏效。

來源

2011-10-19 23:13:44

除非有例外 –

-1

是的，它應該工作。我沒有看到任何問題。

來源

2011-10-19 23:14:03

除非有例外 –

不，它可能不會，如果引發異常。一個更好的（更常見）的選擇是：

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

來源

2011-10-19 23:14:10

+1例外和線程安全 – Flexo

爲了更方便和

例外安全
線程安全
支持tree recursion

（！）

_{如果你真的展現了你的想象力，這可以使編譯器更容易嵌入一些遞歸調用，和/或在尾遞歸情況下執行尾部調用優化。我沒有證據表明這起着的作用，但我可以想象從影響編譯器優化的函數體內引用外部符號。}

我建議：

stuff recurse(int level=0) 
{ 

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

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

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

    //... (return stuff?) 

}

來源

2011-10-19 23:14:14 sehe

我認爲他的原始計劃也可以用於樹遞歸 –

@MooingDuck你是對的。我習慣於在異步/推拉環境下思考這些天。（想象一下，將一個lambda回調傳遞給嵌套的調用，靜態深度將被視爲在lambda中更新，這不是一種常見的情況，我猜:)） – sehe

如果你想做到這一點非侵入每一個電話，你其實可以問你的編譯器的儀器給你，例如用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; 
}

您需要與-finstrument-functions爲此工作進行編譯。

來源

2011-10-19 23:22:46 Flexo

這是編譯器特有的，因此是不可移植的代碼。 – harper

您通常希望增加一個深度變量，該變量在遞歸函數之外爲了線程安全的目的而定義，並從該函數之外打印。

這裏有一個簡單的階乘的例子展示了它：

#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; 
}

輸出：

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

來源

2011-10-19 23:53:14

如何跟蹤遞歸深度？

回答

相關問題