这段代码到底发生了什么?
我有一个包含递归函数的代码。 我在递归上浪费了很多时间,但我仍然无法得到它:
#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 = 1
。 address 102
和m = 1
被推入堆栈,并且从m = 0
address 100
再次执行该function。 由于m = 0
我们执行address 102
并在控制台上打印0。 函数结束并且弹出最后返回address (102)
和参数m = 1
,并且在屏幕上执行打印1的address 102
处的行。
- 使用整数参数
10
调用函数count
。 - 由于函数参数
m
(大于10
)大于0
因此函数count
使用整数参数m
调用自身,该参数为10
减1
,等于9
。 - 步骤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 . .
通过更改用于计算的一些数据,我们可以返回并再次读取相同的指令并获得不同的结果。 递归函数的抽象允许我们以一种很好的“按值调用”的方式操作我们想要改变的数据,这样我们就不会无意中覆盖它。
这是由编译器在将调用函数的状态存储在堆栈上时完成的,因此我们不必手动存储它。