通过学习C语言可以提示这个问题。

我在数据结构 class 中看到,在许多情况下,递归被证明是一种快速简便的解决方案(例如,快速排序,遍历二叉搜索树等),其中明确提到使用自创建堆栈会更好理念。

给出的原因是,递归需要许多函数调用,而函数调用“速度较慢”。

但是,随着任何函数调用都使用堆栈,使用自创建堆栈如何证明更好呢?

最佳答案

自我创建的堆栈比执行堆栈更有效的原因有两个:

  • 执行堆栈旨在处理调用新函数的一般情况。这意味着它有很多开销:它必须包含指向前一个函数的指针,它必须包含指向堆上的值的指针,以及许多其他簿记项目。如果您的计算确实是特定的,那么这可能会超出您对特定计算的需求。所有其他管理都会降低效率。在函数非常繁重且调用相对较少的情况下,这很好。在函数本身更简单但有许多函数调用的情况下,开销成本成比例地增加。
  • 通用堆栈为您隐藏了许多细节,从而使无法利用直接引用堆栈的不同部分的优势。例如,堆栈的根对您隐藏了。假设您正在使用递归在大树中搜索特定值。在某个时候,您在树的深处有一千个节点,您便找到了值。成功!但是随后您必须一次从树中爬出一个函数:这意味着至少要进行一千次调用才能返回该值。 (*)相反,如果您编写了自己的堆栈,则可以立即返回。或者,假设您有一个算法,在树中的某些节点上,需要您在继续执行之前备份n堆栈帧。使用通用堆栈框架,您需要退出这些框架,直到找到所需的框架为止。如果您是专门为算法设计堆栈的,则可以提供一种机制,以一种指令而不是n的方式立即跳转到执行点。

  • 因此,当您可以利用抛弃不需要的,但是花费时间的通用堆栈框架机制的某些部分,或者编写的算法可以利用在堆栈中快速移动的优势时,应该编写自己的堆栈。如果它知道自己在做什么,则使用它(在这里,通用堆栈通过隐藏它的抽象来“保护”您执行此操作)。请记住,函数调用只是用于处理代码的特定通用抽象:如果由于某种原因它们添加了使您的代码笨拙的约束,则可以创建一个精简版本以更直接地满足您的需求。

    如果分配给堆栈的内存与必须递归的次数相比较小,那么您也可能会创建自己的堆栈,例如,如果您的输入域很大,或者运行在专用的小尺寸硬件或类似的情况。同样,这取决于您正在运行的算法以及通用堆栈解决方案如何帮助或阻碍它。

    (*)尾递归通常会有所帮助,但是由于定义上尾递归仅进入更深一层的堆栈帧,因此我假设您所谈论的情况是严格不可能的。

    07-24 09:51
    查看更多