0

我遇到了一些我以前没见过的东西。我有以下递归函数，仅在i静态时才有效

void printNthFromLast(Node* head, int n) {

    static int i = 0;

    if(head == nullptr)
        return;

    printNthFromLast(head->next, n);

    if(++i == n)
        cout << head->data;
}

我假设在这种情况下静态意味着在对同一函数的多个递归调用之间共享 printNthFromLast？

真正令人困惑的部分是它不会在每次递归函数调用自身时将其重新初始化为 0。好像这整行代码static int i = 0;都被跳过了？

谁可以给我解释一下这个？

4

7 回答 7

2

您观察到的行为：

真正令人困惑的部分是它不会在每次递归函数调用自身时将其重新初始化为 0。这就像整行代码 static int i = 0; 被跳过？

正是您对静态的要求。局部静态变量在第一次达到其定义（即行static int i = 0;）时被初始化。

在您的情况下，这意味着它只会在程序的整个运行时第一次调用此方法时设置为零。没有对同一个函数进行多次递归调用的概念，因此如果该方法是由自身调用（您所指的多次递归调用）或者如果您在其他地方开始一个全新的递归堆栈，则没有区别你的客户代码。

可能的解决方案

回到您的描述，它只适用于 i 是静态的（对于 n！=1），因为如果您删除了static关键字，那么每次输入该方法时 i 将被初始化为零（ i 的不同本地实例对于方法的每次调用）。因此在你的情况下

  if(++i == n)

++i将始终评估为 1，与递归深度无关。

如果您希望每次在客户端代码中调用您的方法时都重新初始化静态 i （即开始一个新的递归堆栈），您可以这样编写：

void printNthFromLast(Node* head, int n, bool reinit=true)
{

   static int i = 0;

   if(reinit)
   {
       i=0;
   }

   if(head == nullptr)
      return;

   printNthFromLast(head->next, n, false);

   if(++i == n)
       cout << head->data;
}

带有尾调用优化的线程安全

更简洁的解决方案是将 i 作为函数的可变参数，因此您的函数将是线程安全的。并且通过更好的操作顺序，您无需保存先前的调用帧，从而享受大多数最新编译器提供的尾调用优化。

编辑：正如 Matthieu 所指出的，我最初的实现打印了第 N 个元素而不是最后一个元素的第 N 个。在启用 TCO 的同时进行修复不太优雅，但可以按如下方式完成：

/// n==1 means printing the last element here
static void printNthFromLastImpl(const Node* currentNode, const Node* offsetNode, const int n, int currentDepth)
{
    // n == 0 will never print in the original example by op, so forbid it
    assert(n);
    
    if(++currentDepth > n)
    {
        offsetNode = offsetNode->next;
    }
    
    if(currentNode->next)
    {
        currentNode = currentNode->next;
    }
    else
    {
        if(currentDepth >= n)
        {
            cout << offsetNode->data;
        }
        return;
    }
  
  
    return printNthFromLastImpl(currentNode, offsetNode, n, currentDepth);
}

/// \brief : code to call from client
static void printNthFromLast(const Node* head, const int n)
{
    if (head)
    {
        printNthFromLastImpl(head, head, n, 0);
    }
}
于 2013-08-07T09:14:07.573 回答
2

当你声明一个static局部变量时，编译器只初始化一次（控制流第一次通过变量声明）；此后，该变量在程序的整个生命周期内对声明它的函数的所有调用都保持其值，就像全局变量一样。

这是如何实现的？

当编译器看到这样的东西时：

void foo() {
    static int i = 0;

    cout << i++;
}

它产生与此等效的代码：

bool foo_i_initialized = false; // global
int foo_i; // global

void foo() {
    if (!foo_i_initialized) {
        foo_i = 0;
        foo_i_initialized = true;
    }

    cout << foo_i++;
}

上面的例子有点做作，因为这里foo_i是一个用常量初始化的原语，因此它可以在全局范围内静态初始化（不需要布尔标志），但这种机制也可以处理更复杂的场景。

于 2013-08-07T09:16:03.557 回答
1

因此，如前所述，static int i = 0;它是函数的局部变量。它在流控制第一次通过其定义时被初始化，并在此后被跳过。提出了两种特殊情况：

  • 在引发异常的动态初始化（通过函数）的情况下，将在下一次流控制通过定义时重新尝试初始化。
  • 在来自多个线程的调用的情况下，第一个线程进行初始化，所有其他线程都被阻塞，直到它完成（或因异常而失败）

现在，关于您的代码：不要。局部静态是变相的全局变量，您的代码相当于：

int i = 0;

void printNthFromLast(Node* head, int n) {    
    if(head == nullptr)
        return;

    printNthFromLast(head->next, n);

    if(++i == n)
        cout << head->data;
}

注意：不仅更难调试，而且也不是线程安全的。

相反，您应该为此用法提供一个局部变量：

static void printNthFromLastImpl(Node const* const head, int& i, int const n) {
    if(head == nullptr)
        return;

    printNthFromLastImpl(head->next, i, n);

    if(++i == n)
        cout << head->data;
}

// Each call to this function instantiates a new `i` object.
void printNthFromLast(Node const* const head, int const n) {
    int i = 0;
    printNthFromLastImpl(head, i, n);
}

编辑：正如Ad N所说，由于列表没有被修改，它应该通过const指针传递。

在 Ad N 最新编辑（TCO 版本）之后，我意识到迭代实现应该可以工作（注意，可能会有一些错误）。

void printNthFromLast(Node const* const head, int const n) {
    if (n == 0) { return; }

    // Set "probe" to point to the nth item.
    Node const* probe = head;
    for (int i = 0; i != n; ++i) {
        if (probe == nullptr) { return; }
        probe = probe->next;
    }

    Node const* current = head;

    // Move current and probe at the same rhythm;
    // when probe reaches the end, current is the nth from the end.
    while (probe) {
        current = current->next;
        probe = probe->next;
    }

    std::cout << current->data;
}
于 2013-08-07T09:39:12.860 回答
1

初始化仅在第一次调用函数时执行。后续调用将使用已经初始化的值。

于 2013-08-07T09:11:49.227 回答
0

不仅在多个递归调用之间共享，在所有调用之间共享。

变量实际上只有一个实例i，并且在函数的所有调用中共享。

于 2013-08-07T09:13:37.650 回答
0

你自己描述的很好。静态变量只初始化一次，第一次是通过函数，然后变量在函数调用之间共享。

于 2013-08-07T09:11:43.140 回答
0

声明为静态的变量只初始化一次。因此，即使再次调用该函数时，在此上下文中的变量 i 的值也会从先前的调用中保留下来。
下次程序到达初始化变量的静态初始化语句时，它会跳过该语句。由于静态变量存储在 BSS 段中而不是堆栈中，因此不会更改先前函数调用中变量的先前状态。

于 2013-08-07T09:12:00.523 回答