理解遞歸用C

Question

這是一個遞歸程序。但我不明白此程序期間發生的事件的序列

#include<stdio.h> 
count(int); 
main() 
{ 
    int x=5; 
    count(x); 
} 
count(int y) 
{ 
    if(y>0) 
    { 
     count(--y); 
     printf("%d ",y); 
    } 
} 

輸出爲：

4 3 2 1 0 ... 

但我不明白的時候第一次count(5)叫什麼發生，當count（4）被調用時。控件是否立即進入函數的開始？或者，第一它打印的y值，然後再進入到功能count()的開始？

Answer 1

您可以輕鬆地單步執行代碼，看看那裏發生了什麼，稍微用編輯的代碼：

#include<stdio.h> 

void count(int); 

int main() 
{ 
    int x=5; 
    count(x); 
} 
void count(int y) 
{ 
    if(y>0) 
    { 
     count(--y); 
     printf("%d ",y); 
    } 
} 

現在看到的執行過程中發生了什麼。請參閱gdb會話：

(gdb) b count 
Breakpoint 2 at 0x4004ea: file rc.c, line 10. 
(gdb) c 
Continuing. 

Breakpoint 2, count (y=5) at rc.c:10 
(gdb) c 
Continuing. 

Breakpoint 2, count (y=4) at rc.c:10 
(gdb) c 
Continuing. 

Breakpoint 2, count (y=3) at rc.c:10 
(gdb) c 
Continuing. 

Breakpoint 2, count (y=2) at rc.c:10 
(gdb) c 
Continuing. 

Breakpoint 2, count (y=1) at rc.c:10 
(gdb) c 
Continuing. 

Breakpoint 2, count (y=0) at rc.c:10 
(gdb) bt 
#0 count (y=0) at rc.c:10 
#1 0x00000000004004fe in count (y=0) at rc.c:12 
#2 0x00000000004004fe in count (y=1) at rc.c:12 
#3 0x00000000004004fe in count (y=2) at rc.c:12 
#4 0x00000000004004fe in count (y=3) at rc.c:12 
#5 0x00000000004004fe in count (y=4) at rc.c:12 
#6 0x00000000004004dd in main() at rc.c:6 
(gdb) 

回溯描述整個歷史。看到每個呼叫計數是「堆疊」。但沒有人回來。還沒有打印。

現在看看他們是如何返回一個接一個：與他們的價值觀變量，函數與函數的代碼調用，條件上的常數：

(gdb) n 
count (y=0) at rc.c:13 /* count(y = 0) returned first , it will not cause any printing*/ 
(gdb) n 
(gdb) n 
count (y=1) at rc.c:13 /* count(y = 1) returned second, this will cause printing 0 */ 
(gdb) n 
(gdb) n 
count (y=2) at rc.c:13 /* subsequent returns will cause printing of 1,2,3 etc */ 
(gdb) n 
(gdb) n 
count (y=3) at rc.c:13 
(gdb) n 
(gdb) n 
count (y=4) at rc.c:13 
(gdb) c 
Continuing. 
0 1 2 3 4 

Answer 2

那麼它就像一個等差數列。 與N> 0，並在每個時間一個。減去開始直到達到0。 更遞歸這裏（用階乘的例子，你就會明白）： http://en.wikipedia.org/wiki/Recursion

希望這有助於。

問候。

Answer 3

它就像小菜一疊。

1  2   3   4   5 
             count(0) 
          count(1) count(1) 
        count(2) count(2) count(2) 
     count(3) count(3) count(3) count(3) 
main main  main  main  main 


count(0) prints nothing 

轉到步驟4

count(1) prints 1 

轉到步驟3

count(2) prints 2 ... 

所以得到的4 3 2 1你需要交換count(--y)和printf("%d",y)線周圍的輸出。

Answer 4

void count(int y) 
{ 
    if(y>0) 
    { 
     printf("%d ",--y); 
     count(y); 
    } 
} 

打印Y-1，Y-2，... 0

如果y <= 0，那麼就沒有做。如果y > 0，它遞減y打印出遞減y，然後調用count與y的遞減值打印剩餘價值。

又如，這樣：

void count(int y) 
{ 
    if(y>0) 
    { 
     printf("%d ",--y); 
     count(y); 
     printf("amol"); 
    } 
} 

打印Y-1，Y-2，... 0 ... AMOL AMOL（Y次）。

它通過打印y-1，然後遞歸調用count(y-1)打印y-2，.0，amol（y-1次），然後打印剩餘的「amol」。

Answer 5

程序可以通過與它們的等同替換的東西轉化選定的代碼。例如，

main() 
{ 
    int x=5; 
    count(x); 
} 

- >

main() 
{ 
    count(5); 
} 

- >

main() 
{ 
    if(5>0) 
    { 
     count(4); 
     printf("%d ",4); 
    } 
} 

- >

main() 
{ 
    count(4); 
    printf("%d ",4); 
} 

- >

main() 
{ 
    if(4>0) 
    { 
     count(3); 
     printf("%d ",3); 
    } 
    printf("%d ",4); 
} 

- >

main() 
{ 
    count(3); 
    printf("%d ",3); 
    printf("%d ",4); 
} 

- > - >

main() 
{ 
    count(0); 
    printf("%d ",0); 
    printf("%d ",1); 
    printf("%d ",2); 
    printf("%d ",3); 
    printf("%d ",4); 
} 

- >

main() 
{ 
    if(0>0) 
    { 
     count(-1); 
     printf("%d ",-1); 
    } 
    printf("%d ",0); 
    printf("%d ",1); 
    printf("%d ",2); 
    printf("%d ",3); 
    printf("%d ",4); 
} 

- >

main() 
{ 
    printf("%d ",0); 
    printf("%d ",1); 
    printf("%d ",2); 
    printf("%d ",3); 
    printf("%d ",4); 
}