为什么递归会返回到第一个函数？

Question

非常抱歉询问一个已经讨论多次的基本问题，我无法找到答案。我尝试在论坛中搜索相关的问题但没有找到确切的答案（或者我没有理解）。

为什么这个函数在不同的顺序调用时会将 i 到 10 的数字打印两次？难道它不应该按照相同的顺序打印出来吗？我一直听说递归是这样工作的：每个函数在其代码中调用另一个相同的函数，只是应用于更小的域，直到满足结束条件。此时它应该返回（回溯）到原始函数；这就是我不理解的地方，为什么它会返回（不是作为语法调用）到主函数。

void count(int i){
    if(i < 10){
          printf("%d\n", i);
          count(i + 1);
          printf("%d\n", i);
    }
}    

谢谢。

- user3338768

---

运行你的代码通过调试器并逐行单步执行，你会找到答案 ;) - user376507

请不要标记问题为“已解决”。相反，接受最有帮助的答案并保持标题不变。 - Eric Lippert

@EricLippert 好的，我是新来的，不知道规则，谢谢提醒。 - user3338768

没问题。请参考http://meta.stackexchange.com/questions/116101/is-it-ok-to-add-solved-to-the-title-of-a-question以了解此用法的讨论。 - Eric Lippert

Answer 1

一次与7的通话：

count(7)
    output 7
    count(8)
        output 8
        count(9)
            output 9
            count(10)
                end
            output 9
            end
        output 8
        end
    output 7
    end

为什么它不能返回呢？
每次函数调用都会返回，即使是递归函数。

- deviantfan

---

一个递归函数会返回结果，如果它有终止条件，否则你需要检查当前选项卡的地址 ;) - halex

我明白了，所以当满足结束条件时，最后一个函数被返回，然后是倒数第二个，依此类推直到第一个。出于某种原因，我认为每个函数在调用下一个函数后立即返回，显然是错误的。现在一切都清楚了。 - user3338768

Answer 2

与任何函数调用一样，最后，执行会在下一行开始：

 printf("%d\n", i);
 // into the function
 count(i + 1);
 // out of the function
 printf("%d\n", i);

重要的是要知道，i 的值不会被更新。它们不是同一个变量。有十个不同的“版本”i。

 printf("%d\n", i); // i is 3
 count(i + 1);
 printf("%d\n", i); // i is still three, but a version of the function just ran where i is 4

如果你想象一下在看到count(i + 1)时只是粘贴代码，那么在展开count(8)时会得到以下结果：

if(8 < 10){
      printf("%d\n", 8);
      count(8 + 1);
      printf("%d\n", 8);
}

现在粘贴：

if(8 < 10){
    printf("%d\n", 8);
    if(9 < 10){
        printf("%d\n", 9);
        count(9 + 1);
        printf("%d\n", 9);
    }
    printf("%d\n", 8);
}

再次提醒：

if(8 < 10){
    printf("%d\n", 8);
    if(9 < 10){
        printf("%d\n", 9);
        if(10 < 10){
            // we'll never get here
        }
        printf("%d\n", 9);
    }
    printf("%d\n", 8);
}

这是实际运行的代码。旧的i值不会改变。最终，您将拥有来自所有不同函数调用时间的10个不同的i变量。

- Damien Black

---

现在一切都清楚了，每个函数都从“最小的”返回到第一个函数。这就是我之前没有理解的地方。 - user3338768