recursion如何在C中工作

我是C新手,我正在阅读关于recursion,但我完全困惑。

我感到困惑的主要部分是在退出条件达到时事情如何放松。 我想知道如何在recursion值被推出并从堆栈中popup。

也可以请任何人给我一个recursion的图解视图?

谢谢…

让我们假设一个函数:

int MyFunc(int counter) { // check this functions counter value from the stack (most recent push) // if counter is 0, we've reached the terminating condition, return it if(counter == 0) { return counter; } else { // terminating condition not reached, push (counter-1) onto stack and recurse int valueToPrint = MyFunc(counter - 1); // print out the value returned by the recursive call printf("%d", valueToPrint); // return the value that was supplied to use // (usually done via a register I think) return counter; } } int main() { // Push 9 onto the stack, we don't care about the return value... MyFunc(9); } 

输出结果是:0123456789

第一次通过MyFunc,计数是9.它终止检查(它不是0)失败,所以调用recursion调用,(计数器-1),8。

这样每次重复,递减推入堆栈的值,直到计数器== 0.此时,终止子句触发,函数只是简单地返回计数器(0)的值,通常在寄存器中。

下一个调用堆栈,使用返回的值打印(0),然后返callback用(1)时提供给它的值。 这重复:

下一个调用堆栈,使用返回的值打印(1),然后返callback用(2)时提供给它的值。 等等,直到你到达顶部..

所以,如果MyFunc被调用3,你会得到相当于(忽略堆栈中的返回地址等):

 Call MyFunc(3) Stack: [3] Call MyFunc(2) Stack: [2,3] Call MyFunc(1) Stack: [1,2,3] Call MyFunc(0) Stack: [0,1,2,3] Termination fires (top of stack == 0), return top of stack(0). // Flow returns to: MyFunc(1) Stack: [1,2,3] Print returned value (0) return current top of stack (1) // Flow returns to: MyFunc(2) Stack: [2,3] Print returned value (1) return current top of stack (2) // Flow returns to: MyFunc(3) Stack: [3] Print returned value (2) return current top of stack (3) // and you're done... 

在Crecursion就像普通的函数调用一样。

  1. 当一个函数被调用时,参数,返回地址和帧指针(我忘记了顺序)被压入堆栈。
  2. 在被调用函数中,首先将局部variables的空间“推”到堆栈上。
  3. 如果函数返回的东西,把它放在一个特定的寄存器(取决于体系结构,AFAIK)
  4. 撤消步骤2。
  5. 撤消步骤1。

所以,recursion步骤1和2执行几次,然后可能3(也许只有一次),最后4和5完成(多次1和2)。

当退出条件达到时,情况如何放松?

首先,关于recursion的几句话:用于复杂任务的分而治之的方法 ,可以逐渐分解并简化为初始任务的简单实例,直到达到允许直接计算的forms基本情况 。 这是一个与math归纳密切相关的概念。

更具体地说, recursion函数直接或间接地调用它自己。 在直接recursion函数中, foo()会对自己进行另一个调用。 在间接recursion中,函数foo()对函数moo() foo()进行调用,函数moo()继而调用函数foo() ,直到达到基本情况,然后,最终结果按照与初始recursion完全相反的顺序函数调用。

例:

因子n ,记为n! ,是从1n的正整数的乘积。 因子可以被正式地定义为:
阶乘(0)= 1 ,( 基本情况
阶乘(n)= n *阶乘(n-1) ,对于n> 0 。 ( recursion调用

recursion在这个定义中出现,因为我们用阶乘(n-1)定义了factrorial(n

每个recursion函数都应该有终止recursion的终止条件 。 在这个例子中,当n = 0时 ,recursion停止。 上面用C表示的函数是:

 int fact(int n){ if(n == 0){ return 1; } return (n * fact(n-1)); } 

这个例子是一个直接recursion的例子。

这是如何实施的? 在软件层面,其实施与实施其他function(程序)没有区别。 一旦你明白每个过程调用实例与其他过程调用实例是不同的,那么recursion函数本身调用的事实并没有什么大的不同。

每个活动的过程维护一个激活logging ,该logging存储在堆栈中。 激活logging由参数调用者的返回地址局部variables组成

当一个过程被调用时,激活logging就会存在,并在过程终止并且结果返回给调用者之后消失。 因此, 对于没有终止的每个过程,存储包含该过程的状态的激活logging 。 激活logging的数量以及运行程序所需的堆栈空间量取决于recursion的深度。

也可以请任何人给我一个recursion的图解视图?

下图显示阶乘(3)的激活logging

在这里输入图像描述

从图中可以看出,每次调用阶乘都会创build一个激活logging,直到达到基本情况,并从那里开始,我们以结果的forms累积结果。


一个替代的答案是一般你不知道。 C作为一种语言没有任何堆栈。 您的编译器使用称为堆栈的内存位置来存储控制stream信息(如堆栈帧,返回地址和寄存器),但C中没有任何内容禁止编译器在其他位置存储该信息。 以前的答案是正确的。 这就是C编译器今天的运作方式。