c - 递归如何在 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);
}

输出为:012345678

第一次通过MyFunc，count为9，终止检查失败(不是0)，所以调用递归调用，(counter -1), 8.

这样重复，每次递减压入堆栈的值，直到 counter == 0。此时，终止子句触发，该函数仅返回计数器 (0) 的值，通常在寄存器中。

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

下一次调用堆栈，使用返回值打印 (1)，然后返回调用时提供给它的值 (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...