2015-02-12 229 views
-3

考慮下面的遞歸C函數。如何查找遞歸函數自己調用的次數?

void get (int n) { 
    if (n<1) return; 
    get (n-1) ; 
    get (n-3) ; 
    printf ("%d", n) ; 
    } 

如果get(6)功能被稱爲main()那麼有多少次將get()函數返回到主0之前被調用?

+5

這將取決於(全局?)變量'l'的值,我認爲... – glglgl 2015-02-12 06:38:37

+4

我建議放入一個計數器(一個靜態變量),每次輸入'get()'時都會增加。 – Gabe 2015-02-12 06:39:05

+3

@glglgl:我猜這是一個錯字 - 'l'應該是'1'(ell應該是一個) – Gabe 2015-02-12 06:39:50

回答

5

要計算函數被調用的次數,每次輸入函數時都會增加一個靜態計數器,並在調用後打印出該值。例如:

int counter; 
void get (int n) { 
    ++counter; /* increment counter before first return */ 
    if (n<1) return; 
    get (n-1) ; 
    get (n-3) ; 
    printf ("%d", n) ; 
} 

int main() 
{ 
    counter = 0; /* reset counter before each use */ 
    get(6); 
    printf("get() was called %d times\n", counter); 
} 
+1

FWIW,不需要在'main()'中初​​始化'counter'。 C中的全局變量[保證初始化爲零](http://stackoverflow.com/q/16015656/119527)。 – 2015-02-12 07:06:38

+2

@JonathonReinhart:你是對的,但我想讓代碼可以重用;也就是說,您可以在循環中調用它,或者複製/粘貼它以查看使用不同的輸入參數調用函數的次數。 – Gabe 2015-02-12 07:21:59

+0

@JonathonReinhart編寫依賴靜態存儲持續時間的對象隱式零初始化的代碼是非常糟糕的做法。危險,難以維護,令人困惑。 – Lundin 2017-02-08 07:42:37

3

考慮到這當然是一個學術活動,它可能是你理解遞歸如何工作。

我們可以修改代碼以打印出調用樹,顯示每個調用:

#include <stdio.h> 

void get(int n, int depth) 
{ 
    static int call = 1; 
    printf("%3d: %*sget(%d)\n", call++, 2*depth, "", n); 
    if (n<1) 
     return; 
    get(n-1, depth+1); 
    get(n-3, depth+1); 
} 

int main(void) 
{ 
    get(6, 0); 
    return 0; 
} 

輸出:

1: get(6) 
    2: get(5) 
    3:  get(4) 
    4:  get(3) 
    5:   get(2) 
    6:   get(1) 
    7:    get(0) 
    8:    get(-2) 
    9:   get(-1) 
10:   get(0) 
11:  get(1) 
12:   get(0) 
13:   get(-2) 
14:  get(2) 
15:  get(1) 
16:   get(0) 
17:   get(-2) 
18:  get(-1) 
19: get(3) 
20:  get(2) 
21:  get(1) 
22:   get(0) 
23:   get(-2) 
24:  get(-1) 
25:  get(0) 

請注意,我假設你的作業狀態if (n<1)(「一個「),而不是if (n<l)(」ell「)。另外請注意,我添加了一個depth參數。這允許我適當地縮進每個呼叫。