递归如何在 C 中工作 [英] How Recursion works in C

问题描述

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

I am new to C and I'm reading about recursion, but I am totally confused.

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

The main part where I'm getting confused is how things get unwind when the exit condition is reached. I would like to know how during recursion values got pushed and popped from stack.

谁能给我一个递归的示意图?

Also can anyone please give me a diagramatic view of 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);
}

输出为:012345678

The output is: 012345678

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

The first time through MyFunc, count is 9. It fails the terminating check (it is not 0), so the recursive call is invoked, with (counter -1), 8.

如此重复，每次递减压入堆栈的值，直到counter == 0.此时，终止子句被触发，函数简单地返回计数器 (0) 的值，通常在寄存器中.

This repeats, decrementing the value pushed onto the stack each time until counter == 0. At this point, the terminating clause fires and the function simply returns the value of counter (0), usually in a register.

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

The next call up the stack, uses the returned value to print (0), then returns the value that was supplied into it when it was called (1). This repeats:

下一次调用堆栈，使用返回值打印 (1)，然后返回调用时提供给它的值 (2).以此类推，直到到达堆栈顶部.

The next call up the stack, uses the returned value to print (1), then returns the value that was supplied into it when it was called (2). etc, till you get to the top of the stack.

因此，如果使用 3 调用 MyFunc，您将获得等效的(忽略堆栈中的返回地址等):

So, if MyFunc was invoked with 3, you'd get the equivalent of (ignoring return addresses etc from the stack):

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

这篇关于递归如何在 C 中工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！