这段代码到底发生了什么?

我有一个包含递归函数的代码。 我在递归上浪费了很多时间,但我仍然无法得到它:

#include void count(int); int main() { int x=10,z; count(x); } void count(int m) { if(m>0) count(m-1); printf("%d",m); } 

当参数为10调用第一次count ,它满足条件,然后启动递归部分。 当函数调用自身时会发生什么? 我不明白。 请参考堆栈进行解释。

m大于0时,我们称为count 。 这是堆栈调用的表示:

  count (m = 10) count (m = 9) count (m = 8) count (m = 7) count (m = 6) count (m = 5) count (m = 4) count (m = 3) count (m = 2) count (m = 1) count (m = 0) printf 0 printf 1 printf 2 printf 3 printf 4 printf 5 printf 6 printf 7 printf 8 printf 9 printf 10 

下次它自称它有一个较小的值

 count(int m) { if(m>0) count(m-1); // now it is calling the method "count" again, except m is one less printf("%d",m); } 

所以首先它将调用count为10,然后它将调用9,然后是8,然后是7 …..直到这个if语句不成立:

 if(m>0) 

你可能会感到困惑的是if语句只适用于下一行(printf不是if语句的一部分)

所以你有了:

 count(int m) { if(m>0) { count(m-1); // now it is calling the method "count" again, except m is one less } printf("%d",m); } 

因此,一旦m不> 0,递归调用将停止,然后它将调用printf。

当m为0时调用printf后,它将从’count’调用返回,(返回m等于1),然后当m为1时调用printf,然后当m为2时调用printf ,…..

所以输出应该是:

 "0 1 2 3 4 5 6 7 8 9 10" 

编辑:就堆栈而言:

这就是堆栈正在做的事情:

 count(10) // push count(10) 

– >

 count(9) // push count(9) count (10) 

– >

– >

 count(0) // push count(0) count(1) count(2) count(3) count(4) count(5) count(6) count(7) count(8) count(9) count(10) 

– >(然后它开始打印并从堆栈中弹出方法)

 // pop count(0), and printf(0) count(1) count(2) count(3) count(4) count(5) count(6) count(7) count(8) count(9) count(10) 

– >

 // pop count(1), and printf(1) count(2) count(3) count(4) count(5) count(6) count(7) count(8) count(9) count(10) 

– >

– >

 // pop count(9), and printf(9) count(10) 

– >

 // pop count(10), and printf(10) 

调用函数时,返回地址(下一个要执行的代码)与其当前参数一起存储在堆栈中。 函数完成后,弹出地址和参数,以便cpu知道继续执行代码的位置。

让我们写一下函数的地址(仅出于本例的目的)

 count(int m) { (address = 100) if(m>0) (address = 101) count(m-1); // now it is calling the method "count" again, except m is one less (address = 102) printf("%d",m); } 

对于m = 1:

if是fullfield,因此我们在address 101执行代码, m = 1address 102m = 1被推入堆栈,并且从m = 0 address 100再次执行该function。 由于m = 0我们执行address 102并在控制台上打印0。 函数结束并且弹出最后返回address (102)和参数m = 1 ,并且在屏幕上执行打印1的address 102处的行。

  1. 使用整数参数10调用函数count
  2. 由于函数参数m (大于10 )大于0因此函数count使用整数参数m调用自身,该参数为101 ,等于9
  3. 步骤2以不同的参数(m-1)重复,直到m不大于0 ,程序打印m的值。

递归函数只修改赋给它的参数,并用该修改后的值调用自身,直到返回所需的结果(在这种情况下, m不大于0 )。

每个数字指的是行号。

 #include count(int); main() { 1int x=10,z; 2count(x); } count(int m) { 3if(m>0) 4 count(m-1); 5printf("%d",m); } 

执行就像这样(x = 3) –

行号| x的值

1 3

2 3

3 3

4 2

3 2

4 1

3 1

4 0

5 0

5 1

5 2 2

5 3

屏幕上印有数字0 1 2 3

如果您想要更具体的答案,那么您必须研究编译器的工作原理。 但一般来说编译器会为包含前导码的函数创建机器代码,在此代码中,在堆栈上分配足够的内存(通过递减堆栈指针),可以将函数变量的副本放在堆栈上(我们可以存储函数的状态)。

该函数将存储在寄存器和内存中的值,这些值必须存储在堆栈中以进行每个(递归)调用,否则新调用将覆盖重要数据! 所以基本上机器代码看起来像这样(伪代码)

 //store m on the stack store m,stack_pntr+m_offset //put input values in designated register a0 = m //allocate memory on the stack stackPntr -= stack_size_of(count_vars) //store return address in allocated register //jump to the first instruction of count . . 

通过更改用于计算的一些数据,我们可以返回并再次读取相同的指令并获得不同的结果。 递归函数的抽象允许我们以一种很好的“按值调用”的方式操作我们想要改变的数据,这样我们就不会无意中覆盖它。

这是由编译器在将调用函数的状态存储在堆栈上时完成的,因此我们不必手动存储它。