C语言 递归如何在 C 中工作

How Recursion works in C

提问by Amit Singh Tomar

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

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

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?

也有人能给我一个递归的示意图吗？

Thanks...

谢谢...

回答by forsvarir

Lets assume a function:

让我们假设一个函数：

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);
}

The output is: 012345678

输出为：012345678

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.

第一次通过MyFunc，count 是 9。它没有通过终止检查（它不是 0），所以递归调用被调用，用(counter -1), 8。

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.

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

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:

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

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.

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

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

因此，如果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...

回答by Ziezi

How things get unwind when the exit condition is reached?

当达到退出条件时，事情如何放松？

First, few words about recursion: a divide and conquer methodused for complex tasks that can be gradually decomposed and reduced to a simple instances of the initial task until a form^{(base case)}that allows direct calculation is reached. It is a notion closely related to mathematical induction.

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

More specifically, a recursive functioncalls itself, either directly or indirectly. In direct recursion function, foo(), makes another call to itself. In indirect recursion, function foo()makes a call to function moo(), which in turn calls function foo(), until the base case is reached, and then, the final result is accumulated in the exact reverse order of the initial recursive function call.

更具体地说，递归函数直接或间接调用自身。在直接递归函数中，foo(), 再次调用自身。在间接递归中， functionfoo()调用 function moo()，然后调用 function foo()，直到达到基本情况，然后以与初始递归函数调用完全相反的顺序累积最终结果。

Example:

例子：

Factorial n, denoted n!, is the product of positive integers from 1to n. The factorial can be formally defined as:
factorial(0)=1, (base case)
factorial(n)= n * factorial(n-1), for n > 0. (recursive call)

阶乘n，记为n！, 是从1到n的正整数的乘积。阶乘可以正式定义为：
factorial(0)=1, ( base case)
factorial(n)= n * factorial(n-1)，对于n > 0。（递归调用）

Recursion shows up in this definition as we define factrorial(n)in terms of factorial(n-1).

递归显示了在该定义中，我们定义factrorial（n）的在以下方面阶乘（N-1） 。

Every recursion function should have termination conditionto end recursion. In this example, when n=0, recursion stops. The above function expressed in Cis:

每个递归函数都应该有终止条件来结束递归。在这个例子中，当n=0 时，递归停止。上面用C表达的函数是：

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

This example is an example of direct recursion.

这个例子是一个直接递归的例子。

How is this implemented?At the software level, its implementation is not different from implementing other functions(procedures). Once you understand that each procedure call instanceis distinct from the others, the fact that a recursive function calls itself does not make any big difference.

这是如何实施的？在软件层面，它的实现与实现其他功能（程序）没有区别。一旦您了解每个过程调用实例与其他过程调用实例不同，递归函数调用自身这一事实并没有什么大的区别。

Each active procedure maintains an activation record, which is stored on the stack. The activation record consists of the arguments, return address (of the caller), and local variables.

每个活动过程维护一个活动记录，该记录存储在堆栈中。活动记录由参数、（调用者的）返回地址和局部变量组成。

The activation record comes into existence when a procedure is invoked and disappears after the procedure is terminated and the result is returned to the caller. Thus, for each procedure that is not terminated, an activation record that contains the state of that procedure is stored. The number of activation records, and hence the amount of stack space required to run the program, depends on the depth of recursion.

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

Also can anyone please give me a diagramatic view of recursion?

也有人能给我一个递归的示意图吗？

Next figure shows the activation record for factorial(3):

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

As you can see from the figure, each call to the factorial creates an activation record until the base case is reached and starting from there we accumulate the result in the form of product.

从图中可以看出，对阶乘的每次调用都会创建一个激活记录，直到达到基本情况，并从那里开始以乘积的形式累积结果。

---

---

回答by subsub

In C recursion is just like ordinary function calls.

在 C 中，递归就像普通的函数调用一样。

1. When a function is called, the arguments, return address, and frame pointer (I forgot the order) are pushed on the stack.
2. In the called function, first the space for local variables is "pushed" on the stack.
3. if function returns something, put it in a certain register (depends on architecture, AFAIK)
4. undo step 2.
5. undo step 1.

1. 当一个函数被调用时，参数、返回地址和帧指针（我忘记了顺序）被压入堆栈。
2. 在被调用的函数中，首先将局部变量的空间“压入”堆栈。
3. 如果函数返回一些东西，把它放在某个寄存器中（取决于架构，AFAIK）
4. 撤消第 2 步。
5. 撤消步骤 1。

So, with recursion steps 1 and 2 are performed a few times, then possibly 3 (maybe only once) and finally 4 and 5 are done (as many times as 1 and 2).

因此，递归步骤 1 和 2 执行几次，然后可能执行 3（可能只执行一次），最后执行 4 和 5（次数与 1 和 2 一样多）。

回答by Nikos

An alternative answer is that in general you don't know. C as a language doesn't have any stack of heap. Your compiler uses a memory location called the stack to store control flow information such as stack frames, return addresses and registers, but there is nothing in C prohibiting the compiler to store that information elsewhere. For practical aspects the previous answers are correct. This is how C compilers operate today.

另一个答案是，通常您不知道。C 作为一种语言没有任何堆堆栈。您的编译器使用称为堆栈的内存位置来存储控制流信息，例如堆栈帧、返回地址和寄存器，但 C 中没有任何内容禁止编译器将这些信息存储在其他地方。对于实际方面，以前的答案是正确的。这就是当今 C 编译器的运行方式。

回答by carloswm85

This question has been widely answered. Allow me please to incorporate an additional answer using a more pedagogical approach.

这个问题得到了广泛的回答。请允许我使用更具教学性的方法加入额外的答案。

You can think function recursion as a stack of bubbleswith two differentiate stages: pushing stage and bursting stage.

您可以将函数递归视为具有两个不同阶段的一堆气泡：推动阶段和破裂阶段。

---

---

A) PUSHING STAGE (or "Pushing the stack", as OP call it)

A）PUSHING STAGE（或“推送堆栈”，如OP所称）

0) The starting Bubble #0is the MAIN function. It is blown up with this information:

0) 起始气泡#0是主要功能。它被这些信息炸毁了：

• Local variables.
• The call to the next Bubble #1 (the first call to the recursive function, MYFUNC).

• 局部变量。
• 对下一个 Bubble #1 的调用（对递归函数 MYFUNC 的第一次调用）。

1) Bubble #1is blown up on its turn with this information:

1) Bubble #1在轮到它时被炸毁，并提供以下信息：

• Parameters from the previous Bubble #0.
• Local variables if necessary.
• A returning address.
• Terminating check with a returning value (eg: if (counter == 0) {return 1}).
• A call to the next Bubble #2.

• 来自前一个气泡 #0 的参数。
• 必要时局部变量。
• 返回地址。
• 使用返回值终止检查（例如：if (counter == 0) {return 1}）。
• 调用下一个气泡 #2。

Remember that this bubble, as the other bubbles, is the recursive function MYFUNC.

请记住，这个气泡和其他气泡一样，是递归函数 MYFUNC。

2) Bubble #2is blown up with the same information as Bubble #1, getting from the latter the necessary input (parameters). After this point, you can stack as many bubbles as you want inflating the information accordingly to the listed items in Bubble #1.

2) Bubble #2用与 Bubble #1 相同的信息炸毁，从后者获得必要的输入（参数）。在此之后，您可以根据需要根据 Bubble #1 中列出的项目增加信息来堆叠尽可能多的气泡。

i) So you get as many bubbles as you want: Bubble #3, Bubble #4..., Bubble #i. The very last bubble has a NAIL in the terminating check. Be aware!

i) 所以你会得到尽可能多的气泡：Bubble #3, Bubble #4..., Bubble #i。最后一个气泡在终止检查中有一个 NAIL。意识到！

B) BURSTING STAGE (or "Popping the stack", as OP call it)

B）爆破阶段（或“弹出堆栈”，如OP所称）

This stage happens when you reach the positive terminating check and the last bubble containing the nail is burst.

当您达到肯定的终止检查并且包含钉子的最后一个气泡破裂时，就会发生此阶段。

Let's say this stage happens in Bubble #3. The positive terminating check is reached and Bubble #3 is burst. Then the NAIL from this bubble is liberated. This nail falls on the underneath Bubble #2 and burst it. After this happens the nail follows its fall until it burst Bubble #1. The same happens to Bubble #0. It is important to notice that the nail follows the returning address in the bubble that it's being burst at the moment: the address tells the nail which direction to follow while falling.

假设这个阶段发生在泡沫 #3 中。达到肯定的终止检查并且Bubble #3破裂。然后从这个泡沫中解放出来。这颗钉子落在下面的气泡#2 上并把它爆裂。发生这种情况后，钉子会随之掉落，直到它爆裂气泡 #1。泡泡#0 也是如此。重要的是要注意钉子在它正在破裂的气泡中跟随返回地址：地址告诉钉子在下落时要遵循的方向。

At the end of this process, the answer is obtained and delivered to the MAIN function (or Bubble #0, which of course is not burst).

在此过程结束时，获得答案并将其传递给 MAIN 函数（或 Bubble #0，当然它不是爆裂的）。

---

---

C) GRAPHICALLY (as OP asked)

C）图形（如OP所问）

This is the graphical explanation. It evolves from the bottom, Bubble #0 to top, Bubble #3.

这是图形解释。它从底部，Bubble #0 到顶部，Bubble #3。

/*Bubble #3 (MYFUNC recursive function): Parameters from Bubble #2,
local variables, returning address, terminating check (NAIL),
call (not used here, as terminating check is positive).*/

Pushing up to the bubble above↑ ----------------------------------------------------- Nail falls to Bubble #2

向上推向上气泡↑ ------------------------------------------- ---------- 指甲掉到泡泡#2

/*Bubble #2 (MYFUNC recursive function): Parameters from Bubble #1,
local variables, returning address, terminating check (not used),
call to Bubble #3.*/

Pushing up to the bubble above↑ ----------------------------------------------------- Nail falls to Bubble #1

向上推到↑上方的气泡------------------------------------------- ---------- 指甲掉到泡泡#1

/*Bubble #1 (MYFUNC recursive function): Parameters from Bubble #0,
local variables, returning address, terminating check (not used),
call to Bubble #2.*/

Pushing up to the bubble above↑ ----------------------------------------------------- Nail falls to Bubble #0

向上推到↑上方的气泡------------------------------------------- ---------- 指甲掉到泡泡#0

/*Bubble #0 (MAIN function): local variables, the first call to Bubble #1.*/

---

---

Hope this approach helps someone. Let me know if any clarification is needed.

希望这种方法可以帮助某人。如果需要澄清，请告诉我。