什麼是遞歸，並解釋這個程序的輸出？

Question

我真的不明白這段代碼。當一個函數自己調用它真的發生了什麼？這與棧的概念有關，我知道，但我仍然無法解決這些問題。

#include<stdio.h> 

fun(int); 

main() 
{ 
    int x=3; 
    fun(x); 
} 

fun(int a) 
{ 
    if(a<0) 
    { 
    fun(--a); // what happens when function calls itself 
    printf("%d",a); 
    fun(--a); 
    } 
} 

請解釋在此期間發生的事件的順序。

Answer 1

函數只是駐留在內存某處的代碼。無論何時進行函數調用，編譯器都會將其轉換爲平臺的彙編代碼命令，該函數在函數調用完成後保存要執行的下一個命令的地址，並告訴處理器在內存中何處「跳轉」以讀取下一個要執行的命令。

遞歸的工作原理是因爲您可以輕鬆地告訴處理器「跳回」內存中函數代碼塊的開頭。當前正在調用的函數具有與任何其他函數一樣的內存地址，因此處理器跳轉到內存中當前函數的代碼塊的開頭或內存中的某個其他函數的代碼塊沒有區別。

由於我們需要保存要在完成函數調用後執行的命令的返回地址以及存儲當前函數的參數和自動變量的位置，因此堆棧發揮作用。因此，當你進行連續的函數調用時，會創建一個調用堆棧，它的參數以及堆棧向下增長時先前調用的函數的返回地址將會更高。這被統稱爲該函數的「堆棧幀」。當從函數返回時，當前函數的堆棧幀將從堆棧底部彈出，然後讀取並執行完成該函數後處理器需要跳回的內存地址。在遞歸的情況下，這意味着我們只是跳回到同一個函數的先前版本，但在這種情況下，自動堆棧變量和參數在我們返回後會不同，因爲我們已經返回到先前的堆棧幀該功能的版本。

Answer 2

函數參數通過C中的值傳遞，這意味着每次調用該函數時都會創建臨時局部變量。當函數被遞歸調用時，每次都會創建一組新的變量。但是，遞歸不一定會節省存儲空間，因爲必須維護正在處理的值的堆棧。

Answer 3

在這種情況下，調用fun（）就像調用任何其他函數一樣。例如：

int main() { 
    int a = 0; 
    foo(a); 
    printf("main a = %d\n", a); 
} 

void foo(int a) { 
    a = 1; 
    bar(a); 
    printf("foo a = %d\n", a); 
} 

void bar(int a) { 
    a = 2; 
    printf("bar a = %d\n", a); 
} 

您的來電順序是這樣的：

main(); 
foo(); 
bar(); 

而你的輸出將是這樣的：

bar a = 2 
foo a = 1 
main a = 0 

的參數是按值傳遞的，所以a是抄並且在每個函數中實際上是一個不同的變量。遞歸也一樣。

main(); x = 3 
fun(3); a = 3, so a > 0, nothing happens, return to main() 

如果你要改變的條件很有趣（）調用自身時，> 0（讀自上而下）

main(); x = 3 
fun(3); a = 3, a > 0 so --a = 2, fun(2) 
fun(2); a = 2, a > 0 so --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) /* same as fun(1) above */ 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2)  /* same as fun(1) above */ 

fun(2); printf("%d", a) displays 2, --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0)    /* this is a new fun(1) */ 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2) 

fun(2); nothing left to do so return to fun(3) 

fun(3); printf("%d", a) displays 3, --a = 2, fun(2) /* halfway point */ 
fun(2); a = 2, a > 0 so --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2) 

fun(2); printf("%d", a) displays 2, --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2) 

fun(2); nothing left to do so return to fun(3) 

fun(3); nothing left to do so return to main() 

和你的輸出應該是：1213121反映的樹結構電話：

 3 
    /\ 
    / \ 
    2  2 
    /\ /\ 
    1 1 1 1