C语言中的递归是如何工作的？

Question

我试图了解递归在 C 中是如何工作的。任何人都可以给我解释控制流吗？

#include <stdio.h>
/* printd: print n in decimal */
void printd(int n)
{
  if (n < 0)
  {
    putchar('-');
    n = -n;
  }
  if (n / 10) printd(n / 10);
  putchar(n % 10 + '0');
}

int main()
{
  printd(123);
  return 0;
}

Answer 1

控制流程如下所示（其中 -> 是函数调用）

main()
 └─> printd(123)
      ├─> printd(12)
      │    ├─> printd(1)
      │    │    └─> putchar('1')
      │    └─> putchar('2')
      └─> putchar('3')

Answer 2

Call printd(123)
    (123 / 10) != 0, so Call printd(12)
        (12 / 10) != 0, so Call printd(1)
            (1 / 10) == 0, so Call putchar "1"
        Call putchar "2"
    Call putchar "3"
return 0 (from main())

Answer 3

要了解递归，您需要了解存储模型。尽管有多种变体，但基本上是“自动”存储，用于包含自动变量、参数、编译器临时值和调用/返回信息的存储被安排为“堆栈”。这是一种存储结构，从进程存储中的某个位置开始，并随着过程的调用而“向上”（增加地址）或“向下”（减少地址）“增长”。

可以从几个变量开始：

00 -- Variable A -- 27
01 -- Variable B -- 45

然后我们决定调用过程 X，因此我们生成一个 A+B 参数：

02 -- Parameter -- 72

我们需要保存希望控制返回的位置。假设指令 104 是调用，那么我们将 105 作为返回地址：

03 -- Return address -- 105

我们还需要保存上述“堆栈帧”的大小——四个字，其中 5 个字是帧大小本身：

04 -- Frame size -- 5

现在我们开始在 X 中执行。它需要一个变量C:

05 -- Variable C -- 123

并且需要引用该参数。但它是如何做到这一点的呢？嗯，在入口处，堆栈指针被设置为指向 X 的“堆栈帧”的“底部”。我们可以将“底部”设为多个位置中的任何一个，但让我们将其设为 X 框架中的第一个变量。

05 -- Variable C -- 123  <=== (Stack frame pointer = 5)

但我们仍然需要引用该参数。我们知道，我们的帧“下方”（堆栈帧指针指向的位置）是（按地址递减顺序）帧大小、返回地址，然后是我们的参数。因此，如果我们从 5 中减去 3（对于这 3 个值），我们会得到 2，这是参数的位置。

请注意，此时我们并不真正关心帧指针是 5 还是 55555——我们只是减去引用参数，添加引用我们的局部变量。如果我们想要进行调用，我们将“堆栈”参数、返回地址和帧大小，就像我们在第一次调用时所做的那样。我们可以一次又一次地进行调用，然后继续“推送”堆栈帧。

要返回 we，请将帧大小和返回地址加载到寄存器中。从堆栈帧指针中减去帧大小并将返回地址放入指令计数器中，然后我们回到调用过程。

现在这过于简单化了，有许多不同的方法来处理堆栈帧指针、参数传递和跟踪帧大小。但无论如何，基础知识都适用。

Answer 4

通过将问题分解为 2 个较小的问题，可以在 C（或任何其他编程语言）中实现递归。

你的例子： 打印一个数字可以分为这两个部分

1. 打印第一部分（如果存在
2. ）打印最后一个数字

要打印“123”，更简单的问题是打印“12”（12 是123 / 10) 并打印“3”。
要打印“12”，更简单的问题是打印“1”（1 是 12 / 10）和打印“2”。
要打印“1”，...只需打印“1”。

Answer 5

#include <stdio.h>

#define putd(d) (printf("%d", d))

#define RECURSIVE

void rprint(int n)
{
#ifndef RECURSIVE
    int i = n < 0 ? -n : n;

    for (; i / 10; i /= 10)
        putd(i % 10);

    putd(i % 10);

    if (n < 0)
        putchar('-');
    /* Don't forget to reverse :D */
#else
    if (n < 0) {
         n = -n;
         putchar('-');
    }

    int i = n / 10;
    if (i)
        rprint(i);

    putd(n % 10);
#endif
}

int main()
{
    rprint(-321);
    return 0;
}

Answer 6

递归在堆栈上工作，即先进后出。

递归是一个使用不同参数调用自身直到达到基本条件的过程。当执行过多的递归调用时，就会发生堆栈溢出。

Answer 7

代码：

main()
{print f ("stat");
main();
print f ("end")  ;
}

代码：

main()
{int n, res;
pf("enter n value");
sf("%d",&n);

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