当递归也使用堆栈时，使用堆栈而不是递归如何在 C 中提供更好的性能？
How does using stack instead of recursion give better performance in C when recursion uses stack as well?
这道题是在学习C语言的过程中得到的
我在我的数据结构课程中看到，在许多情况下递归被证明是一种快速简便的解决方案（例如快速排序、二叉搜索树的遍历等），已经明确提到使用自-创建堆栈是一个更好的主意。
给出的原因是递归需要很多函数调用，而函数调用是'slower'。
但是，在任何函数调用都使用堆栈的情况下，使用自创建堆栈如何证明更好呢？
也许出于性能原因，不一定推荐使用自行创建的堆栈。我能想到的一个很好的原因是 "regular" 堆栈可能具有固定大小（通常为 1MB），因此例如对大量数据进行排序会导致 堆栈溢出 。
- 自创堆栈意味着您只需将几个重要变量推送到自创堆栈。
- 当你使用递归时，所有变量的函数头和状态都会被压入堆栈。
如果递归深度很高，使用情况2意味着内存会很快耗尽。
通常，在函数内部的任何事情完成之前，函数调用都会有一些开销。为函数调用生成的代码基本上可以确保您找到您离开时找到的所有内容，好吧，return；同时它在被调用函数内为您提供了一个干净的空白环境。事实上，这种便利是 C 提供的最重要的服务之一，仅次于标准库。 （在许多其他方面，C 只是一个宏汇编程序——您是否曾经并排查看过 C 源代码和生成的汇编程序？）。
特别是通常必须保存一些寄存器，并且可能必须将参数复制到调用堆栈上。所需的努力取决于处理器、编译器和调用约定。例如，参数和 return 值可能在寄存器中，而不是在堆栈中（但是每次递归调用都必须保存参数，不是吗？）。
功能小的话开销比较大；这就是为什么内联可以很强大。内联递归函数调用类似于循环展开。我不知道当前的编译器是否定期这样做（他们可能）。但是依赖编译器是有风险的，所以如果速度很重要，我会避免递归实现琐碎的函数，比如计算阶乘。
自建栈比执行栈更高效的真正原因有两个：
执行堆栈旨在处理调用新函数的一般情况。这意味着它有很多 开销 ：它必须包含指向前面函数的指针，它必须包含指向堆上值的指针，以及许多其他簿记项。如果您的计算确实是特定的，那么这可能比您的特定计算所需的更多。所有额外的管理都会降低效率。在功能很重，调用比较少的情况下，这样是可以的。在函数本身比较简单，但是函数调用很多的情况下，开销成本会不成比例地增加。
广义堆栈向您隐藏了很多细节，阻止您利用直接引用堆栈的不同部分。例如，堆栈的根对您是隐藏的。假设您正在使用递归在一棵大树中搜索特定值。在某个时候，你在树的一千个节点深处，你找到了价值。成功！但是你必须一次从树中爬出一个函数：这意味着至少要调用一千次 才能 return 值 。 (*) 相反，如果您编写了自己的堆栈，则可以立即 return。或者，假设您有一个算法，在树的某些节点处，要求您在继续执行之前备份 n 个堆栈帧。使用通用堆栈帧，您需要退出这些帧，直到找到您要查找的帧。如果你专门为你的算法设计了堆栈，你可以提供一种机制来立即跳转到一条指令的执行点而不是 n。
因此，当您可以利用扔掉不需要但会花费时间的通用堆栈框架机制的部分，或者正在编写的算法可以利用时，您应该编写自己的堆栈如果它知道自己在做什么（在广义堆栈 'protects' 中，你可以通过隐藏它的抽象来做到这一点）。请记住，函数调用只是处理代码的一种特殊的通用抽象：如果出于某种原因它们添加了一个使您的代码变得笨拙的约束，您可能可以创建一个精简版本来更直接地满足您的需求。
如果分配给您的堆栈的内存与您必须递归的次数相比较小，您也可以创建自己的堆栈，例如如果您有一个非常大的输入域或者如果您 运行 在专门的小型硬件或类似情况下。不过，这再次取决于您使用的算法 运行 以及通用堆栈解决方案如何帮助或阻碍它。
(*) 尾递归通常会有所帮助，但由于尾递归根据定义仅进入更深一层的堆栈帧，我假设您正在谈论一种严格不可能的情况。
这道题是在学习C语言的过程中得到的
我在我的数据结构课程中看到，在许多情况下递归被证明是一种快速简便的解决方案（例如快速排序、二叉搜索树的遍历等），已经明确提到使用自-创建堆栈是一个更好的主意。
给出的原因是递归需要很多函数调用，而函数调用是'slower'。
但是，在任何函数调用都使用堆栈的情况下，使用自创建堆栈如何证明更好呢？
也许出于性能原因，不一定推荐使用自行创建的堆栈。我能想到的一个很好的原因是 "regular" 堆栈可能具有固定大小（通常为 1MB），因此例如对大量数据进行排序会导致 堆栈溢出 。
- 自创堆栈意味着您只需将几个重要变量推送到自创堆栈。
- 当你使用递归时，所有变量的函数头和状态都会被压入堆栈。
如果递归深度很高，使用情况2意味着内存会很快耗尽。
通常，在函数内部的任何事情完成之前，函数调用都会有一些开销。为函数调用生成的代码基本上可以确保您找到您离开时找到的所有内容，好吧，return；同时它在被调用函数内为您提供了一个干净的空白环境。事实上，这种便利是 C 提供的最重要的服务之一，仅次于标准库。 （在许多其他方面，C 只是一个宏汇编程序——您是否曾经并排查看过 C 源代码和生成的汇编程序？）。
特别是通常必须保存一些寄存器，并且可能必须将参数复制到调用堆栈上。所需的努力取决于处理器、编译器和调用约定。例如，参数和 return 值可能在寄存器中，而不是在堆栈中（但是每次递归调用都必须保存参数，不是吗？）。
功能小的话开销比较大；这就是为什么内联可以很强大。内联递归函数调用类似于循环展开。我不知道当前的编译器是否定期这样做（他们可能）。但是依赖编译器是有风险的，所以如果速度很重要，我会避免递归实现琐碎的函数，比如计算阶乘。
自建栈比执行栈更高效的真正原因有两个：
执行堆栈旨在处理调用新函数的一般情况。这意味着它有很多 开销 ：它必须包含指向前面函数的指针，它必须包含指向堆上值的指针，以及许多其他簿记项。如果您的计算确实是特定的，那么这可能比您的特定计算所需的更多。所有额外的管理都会降低效率。在功能很重，调用比较少的情况下，这样是可以的。在函数本身比较简单，但是函数调用很多的情况下，开销成本会不成比例地增加。
广义堆栈向您隐藏了很多细节，阻止您利用直接引用堆栈的不同部分。例如，堆栈的根对您是隐藏的。假设您正在使用递归在一棵大树中搜索特定值。在某个时候，你在树的一千个节点深处，你找到了价值。成功！但是你必须一次从树中爬出一个函数：这意味着至少要调用一千次 才能 return 值 。 (*) 相反，如果您编写了自己的堆栈，则可以立即 return。或者，假设您有一个算法，在树的某些节点处，要求您在继续执行之前备份
n个堆栈帧。使用通用堆栈帧，您需要退出这些帧，直到找到您要查找的帧。如果你专门为你的算法设计了堆栈，你可以提供一种机制来立即跳转到一条指令的执行点而不是n。
因此，当您可以利用扔掉不需要但会花费时间的通用堆栈框架机制的部分，或者正在编写的算法可以利用时，您应该编写自己的堆栈如果它知道自己在做什么（在广义堆栈 'protects' 中，你可以通过隐藏它的抽象来做到这一点）。请记住，函数调用只是处理代码的一种特殊的通用抽象：如果出于某种原因它们添加了一个使您的代码变得笨拙的约束，您可能可以创建一个精简版本来更直接地满足您的需求。
如果分配给您的堆栈的内存与您必须递归的次数相比较小，您也可以创建自己的堆栈，例如如果您有一个非常大的输入域或者如果您 运行 在专门的小型硬件或类似情况下。不过，这再次取决于您使用的算法 运行 以及通用堆栈解决方案如何帮助或阻碍它。
(*) 尾递归通常会有所帮助，但由于尾递归根据定义仅进入更深一层的堆栈帧，我假设您正在谈论一种严格不可能的情况。