通过学习C语言可以提示这个问题。
我在数据结构 class 中看到,在许多情况下,递归被证明是一种快速简便的解决方案(例如,快速排序,遍历二叉搜索树等),其中明确提到使用自创建堆栈会更好理念。
给出的原因是,递归需要许多函数调用,而函数调用“速度较慢”。
但是,随着任何函数调用都使用堆栈,使用自创建堆栈如何证明更好呢?
最佳答案
自我创建的堆栈比执行堆栈更有效的原因有两个:
n
堆栈帧。使用通用堆栈框架,您需要退出这些框架,直到找到所需的框架为止。如果您是专门为算法设计堆栈的,则可以提供一种机制,以一种指令而不是n
的方式立即跳转到执行点。 因此,当您可以利用抛弃不需要的,但是花费时间的通用堆栈框架机制的某些部分,或者编写的算法可以利用在堆栈中快速移动的优势时,应该编写自己的堆栈。如果它知道自己在做什么,则使用它(在这里,通用堆栈通过隐藏它的抽象来“保护”您执行此操作)。请记住,函数调用只是用于处理代码的特定通用抽象:如果由于某种原因它们添加了使您的代码笨拙的约束,则可以创建一个精简版本以更直接地满足您的需求。
如果分配给堆栈的内存与必须递归的次数相比较小,那么您也可能会创建自己的堆栈,例如,如果您的输入域很大,或者运行在专用的小尺寸硬件或类似的情况。同样,这取决于您正在运行的算法以及通用堆栈解决方案如何帮助或阻碍它。
(*)尾递归通常会有所帮助,但是由于定义上尾递归仅进入更深一层的堆栈帧,因此我假设您所谈论的情况是严格不可能的。