在递归函数中使用静态

Question

我在编写递归函数时遇到了以下问题：

#include <stdio.h>
void bin_r(unsigned int n)
{
    static int s;
    s++;
    printf("%d", s);
    if (n>1) 
    {
        bin_r(n>>1);
    }
    printf("%d", s);
    // ...
}

int main(void) {bin_r(1777);}

12345678910111111111111111111111111

变量 s 的 'static'-ness 似乎在递归函数调用之前按 (I) 预期的方式工作，但在它之后似乎每次都重新初始化它。对这里发生的事情有什么解释？

如果您想要运行，这里有一个代码示例：https://onlinegdb.com/znV72a6Gw

Answer 1

您在第二次 printf 之前再次调用 bin_r。意思是，只有当条件 (n>1) 为真时，递归才会终止并且堆栈可以展开，执行第二个 printf [无论你有多少递归级别] 次而不会进一步增加 s。

在您的示例中，您有 11 级递归，这就是为什么在满足终止条件后会打印 11 次“11”。

Answer 2

其他 answers/comments 在这里是正确的，但这里是一个基本示例，显示 static 变量可以在基本递归函数中使用的两种不同方式：在自函数之前和之后通话：

static int digits -- used/incremented 在递归函数调用之前。
static int sep -- used/incremented 在递归函数调用之后。

void bin_r(unsigned int n)
{
    // how many total digits -- this will be finished before unwinding the stack
    // here we will increment digits BEFORE the function call, so when the stack
    // is unwound we have the full length / number of digits
    static int digits, sep;
    if (digits==0) printf("%d --> ", n);
    digits++;   

    if (n>1) 
        bin_r(n>>1, level);
    putchar((n&1)==0? '0' : '1'); // == has higher precedence than &

    // unwinding the stack -- separate every four digits from RTL, newline at end
    // here we will increment sep AFTER the function call, so now that we unwind
    // the stack, it will essentially be counting how many frames have been unwound.
    sep ++;
    if (!((digits-sep)%4) && digits != sep) putchar(' ');
    if (digits==sep) {
        putchar('\n');
        digits = sep = 0; // reset statics
    }
}

这里我们使用两种方法来获得我们的输出：

1777 --> 110 1111 0001

在这一行中组合在一起，从右到左每四位分隔二进制数字：

if (!((digits-sep)%4) ...

Answer 3

问题是：

It seems like the 'static'-ness of the variable s works as (I) expected before the recursive function call, but after it it seems to reinitialize it every time. What would be an explanation of what's going on here?

正如我在评论中所说，我没有看到重新初始化的证据。作为一个没有初始化器声明的 static 变量，s 在程序开始时自动初始化为 0。在递归系列的每一步中， s （其中只有一个，而不是每次调用一个）递增然后打印。输入 1777 在 2¹⁰ 和 2¹¹ 之间，因此给定的特定函数递归到深度 11。这会产生

1234567891011

在下山的路上。在返回的路上，s，其值为 11，在每个级别上再次打印而无需进一步修改，额外的

1111111111111111111111

在评论中您还询问了：

And is there a way to keep the static value as it would be before the recursive call (going from 1 to 11) via a static var, or I'd need to use something else for that?

静态局部变量的全部意义在于，它表示函数的所有执行都访问的单个对象。该对象的生命周期与整个程序的生命周期相同，并且与任何对象一样，它会保留其最后存储的值，直到存储一个新值或它的生命周期结束。所以不，没有办法让它在递归的最顶层调用终止后自动重置。而且在函数内部声明，没有链接，不能在函数外直接修改。

一般来说，静态存储持续时间的变量不能很好地玩递归。它们与在多线程程序中使用的访问它们的递归函数不兼容，并且那些在块范围内声明的函数（例如您的 s）很难从声明它们的块外部重置。

可以构建您的 bin_r() 来解决后一个问题，可能像这样：

void bin_r(unsigned int n, _Bool top) {
    static int s;

    s = top ? 1 : (s + 1);
   
    printf("%d", s);
    if (n>1) {
        bin_r(n>>1, 0);
    }
    printf("%d", s);
}

当然，这需要顶层执行的调用者传递 1 来通知函数重置变量。如果您不喜欢那样，那么您可以将该版本的 bin_r 更改为辅助函数，并提供一个单独的非递归函数来正确执行顶级调用。

但是，如果您要这样做，那么为什么不直接删除静态变量呢，也许是这样的：

void bin_r(unsigned int n, int *s) {
    (*s)++;
    printf("%d", *s);
    if (n>1) {
        bin_r(n>>1, s);
    }
    printf("%d", *s);
}

同样，如果您愿意，请为此提供一个单参数包装器。现在您是线程安全的，并且可以完全控制。

在递归函数中使用静态

Using static in a recursive function

c

binary