什么是递归，并解释这个程序的输出？

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