对 C++ 递归感到困惑

Question

我不明白递归如何工作得很好。

void f(int n)
{
  if (n == 1)cout<<1<<" ";
  else
  {
    f(n - 1);
    cout<<n<<" ";
    f(n - 1);
  }

如果我让 n = 4，这将输出1 2 1 3 1 2 1 4 1 2 1 3 1 2 1. 这是为什么？首先，n变得越来越小，直到达到 1，然后会发生什么？我真的无法理解这两个调用的作用，以及为什么第二个调用还在那里，因为第一个调用首先被调用。

Answer 1

递归函数的工作方式与非递归函数完全一样。
特别是，当一个返回时，它返回到它的直接调用者。
也就是说， had 的调用n == 1将返回到had的调用n == 2，后者将返回到 had 的调用，n == 3依此类推，并且调用函数继续以常规方式运行。

您的示例就像这些非递归函数一样工作，您可能会弄清楚其流程：

void f_1()
{
    cout << 1 << " ";
}

void f_2()
{
    f_1();
    cout << 2 << " ";
    f_1();
}

void f_3()
{
    f_2();
    cout << 3 << " ";
    f_2();
}

void f_4()
{
    f_3();
    cout << 4 << " ";
    f_3();
}