递归如何在C中起作用

Question

我是C的新手,我正在阅读有关递归的内容,但我完全感到困惑.

我感到困惑的主要部分是当达到退出条件时,事情是如何放松的.我想知道在递归值中如何从堆栈推送和弹出.

也有人可以给我一个递归的图解视图吗？

谢谢...

Answer 1

让我们假设一个函数:

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,count是9.它没有终止检查(它不是0),所以调用递归调用,使用(counter -1),8.

这会重复,每次都会减少压入堆栈的值,直到counter == 0.此时,终止子句将触发,函数只返回counter(0)的值,通常在寄存器中.

下一次调用堆栈,使用返回值print(0),然后返回调用它时提供给它的值(1).这重复:

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

因此,如果使用3调用MyFunc,则会得到相当于(忽略堆栈中的返回地址等):

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...

Answer 2

达到退出条件后如何放松？

首先,关于递归的几句话:用于复杂任务的分而治之的方法,可以逐步分解并简化为初始任务的简单实例,直到达到允许直接计算的形式^{(基本情况)}.这是一个与数学归纳密切相关的概念.

更具体地说,递归函数直接或间接地调用自身.在直接递归函数中,foo()对自身进行另一次调用.在间接递归中,函数foo()调用函数moo(),函数调用函数foo(),直到达到基本情况,然后,最终结果以与初始递归函数调用完全相反的顺序累加.

例:

因子n,表示为n!,是从1到n的正整数的乘积.阶乘可以形式地定义为:
factorial(0)= 1,(基本情况)
阶乘(n)= n*阶乘(n-1),n> 0.(递归通话)

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

每个递归函数都应该有终止条件来结束递归.在此示例中,当n = 0时,递归停止.用C表示的上述函数是:

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

此示例是直接递归的示例.

这是如何实现的？在软件级别,其实现与实现其他功能(过程)没有区别.一旦你理解了每个过程调用实例与其他过程调用实例不同,递归函数调用自身这一事实并没有产生任何重大影响.

每个活动过程都维护一个激活记录,该记录存储在堆栈中.激活记录由参数,返回地址(调用者)和局部变量组成.

激活记录在调用过程时存在,并在过程终止后消失,并将结果返回给调用者.因此,对于未终止的每个过程,存储包含该过程的状态的激活记录.激活记录的数量,以及运行程序所需的堆栈空间量,取决于递归的深度.

也有人可以给我一个递归的图解视图吗？

下图显示了factorial(3)的激活记录:

从图中可以看出,每次调用阶乘都会创建一个激活记录,直到达到基本情况为止,从那里开始我们以产品的形式累积结果.

Answer 3

在C递归就像普通函数调用一样.

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

因此,使用递归步骤1和2执行几次,然后可能执行3次(可能只执行一次),最后执行4次和5次(多次为1次和2次).