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

我真的无法理解这段代码。 当一个函数调用自己真正发生的事情时？ 我知道它与堆栈的概念有关，但我仍然无法解决这些问题。

#include 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

函数只是驻留在内存中某处的代码。 无论何时进行函数调用，编译器都会将其转换为平台的汇编代码命令，该命令将保存函数调用完成后要执行的下一个命令的地址，并告诉处理器在内存中“跳转”的位置。为了读取下一个要执行的命令。

递归有效，因为您可以轻松地告诉处理器“跳转”回内存中函数代码块的开头。 您正在调用的当前函数具有与任何其他函数一样的内存地址，因此处理器跳转到内存中当前函数的代码块的开头或内存中的某个其他函数的代码块没有区别。

堆栈发挥作用，因为我们需要在完成函数调用后保存命令的返回地址，以及存储当前函数的参数和自动变量的位置。 因此，当您进行连续的函数调用时，会创建一个调用堆栈，如果堆栈向下增长，则会为堆栈中的任何先前调用的函数提供参数和返回地址。 这统称为该function的“堆栈帧”。 从函数返回时，当前函数的堆栈帧从堆栈底部弹出，然后读取并执行处理器在函数完成后需要跳回的内存地址。 在递归的情况下，这意味着我们只是跳回到同一函数的先前版本，但在这种情况下，自我返回后自动堆栈变量和参数将不同，因为我们已返回到先前的堆栈帧该function的版本。

Answer 2

在这种情况下，调用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() 

如果您要更改条件，那么fun>会在> 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 

Answer 3

函数参数在C中通过值传递，这意味着每次调用函数时都会创建临时局部变量。 当递归调用函数时，每次都会创建一组新变量。 但是，递归不一定会节省存储空间，因为必须保留正在处理的值的堆栈。