本地堆栈与调用堆栈

Question

关于复归问题：

创建递归函数时，创建调用堆栈。好吧，没问题；但是，一条关于此页的评论(查找“LKM”的评论)引起了我的好奇心(谷歌没有帮助)：

• 什么是本地堆栈？
• 为什么它会比调用堆栈更快？
• 您将如何实现它(伪代码，js/php/ruby/python都行)？

附属问题(可能需要另一个问题，但我不知道该问哪个问题(.*.)?stack.*.com )：

在这些关于编程的对话中，我经常看到“递归”主题，以及程序员对它的理解有多糟糕。我是自学成才的，我从来不知道大惊小怪是怎么回事。在我的日常编码中，我经常使用递归，不仅是为了解决问题，有时也是因为我认为它们很漂亮。但这些文章让我觉得也许有什么东西我就是看不见。所以：

• 递归有什么好大惊小怪的？有什么不可以不去摸的？

Answer 1

该注释使用的“本地”堆栈意味着隐式声明为局部变量的堆栈。我将通过将它称为“显式”堆栈来区别于调用堆栈。

在不支持递归相关优化(如尾递归)的语言中，显式堆栈上的迭代比递归更快。或者一种语言可能具有有限的堆栈深度。

下面是Eric的一个用一个例子来解释。

Answer 2

LKM只是指一个手动处理的堆栈，例如，一个链接列表，在这个列表中，您将元素推到头部，然后再弹出它们。它会更快，因为它更小，更少的数据在周围乱搞。

它是通过在结构中有一个指向下一个元素的指针(或者引用)和堆栈顶部的head变量来实现的。推送时，可以将push元素的下一个指针设置为head变量的当前值，然后将head变量设置为引用pushed元素。弹出式做的正好相反。

实现它的另一种方法，如果您知道堆栈的最大堆栈，是有一个普通数组和一个索引变量，它告诉数组中的头在哪里。如果您简化了递归调用堆栈，实际上就是这样实现的。

我相信上面提到的大多数语言都有特殊的结构来将数组看作堆栈，通常称为push/pop或shift/unshift。

Answer 3

在这种情况下，使用本地堆栈意味着“使用局部变量，例如像堆栈一样访问的数组”，即FIFO，而不是“创建创建堆栈帧的函数调用，每个调用都包含一个int，所有这些都包含与数组相同的值”。它可以更快一些，因为您避免了推送和弹出寄存器、为每个函数调用设置本地堆栈框架等开销。相反，您只需要进行一个内存分配，仅此而已(如果您使用alloca，那么您的本地堆栈实际上在调用堆栈上-- alloca本质上只是一个in dex增量，而malloc可能涉及各种昂贵的操作)。

与往常一样，权衡的是，通过使堆栈的机器可见，算法的实际递归结构对许多人来说都不那么清晰。请注意，我说的是“很多人”--有些人自然理解递归，有些人则不懂。(我曾经教过Scheme和Prolog给新生，我会说他们中大约有三分之一的人懂递归，三分之二的人不懂。)整个书籍都是为了让后一类学生跨过这个障碍而写的，既然你似乎属于前一类，我不知道我是否能向你传达这个概念对许多人来说是多么的神秘。这甚至不是一个理解发生的步骤顺序的问题，更重要的是一个相信使用一个似乎还没有完成的定义是可能的问题。该解决方案涉及大量的实践和大量的步骤，通过一些中小型的例子。最终，这将使许多学习者的收入下降，尽管到目前为止还不是所有的学生。