Local Stack vs Call Stack

Question

On the matter of Recursion:

When you create a recursive function, you create a call stack. Ok, no problem; However, a comment on this page (look for comments by "LKM") triggered my curiosity (and google was no help):

• What is a local stack?
• Why would it be faster than a call stack?
• How would you actually implement it (pseudo-code, js/php/ruby/python are ok)?

Subsidiary question (might deserve another question, but I don't know on which (.*\.)?stack.*\.com to ask):

In these conversations about programming, I often see the "recursion" theme and how bad/newbie programmers don't grok it. I'm self-taught, and I never understood what the big fuss is all about. I use recursion a lot in my everyday coding, both for solving problems and sometimes just because I think they are beautiful. But these articles make me feel like maybe there is something there I just don't see. So:

• What's all the fuss about recursion? What's there not to grok?

Answer 1

A "local" stack, as that comment uses it, means stack implicitly declared as a local variable. I would differentiate it from the call stack by calling it an "explicit" stack.

Iterating on an explicit stack can be faster than recursion in languages that don't support recursion related optimizations such as tail recursion. Or a language may have limited stack depth.

Here is a good explanation with an example by Eric Lippert.

Answer 2

In this case, using a local stack means "using a local variable, e.g. an array that is accessed like a stack", i.e. FIFO, as opposed to "making function calls, which create stack frames, each of which contains an int, all of which taken together contain the same values as your array would". It can be faster because you're avoiding the overhead of pushing and popping registers, setting up the local stack frame for each function invocation etc. Instead you're doing just one memory allocation and that's it (and if you use alloca then your local stack really is on the call stack - alloca is essentially just an in dex increment, while malloc can involve all sorts of expensive operations).

The trade-off, as always, is that by making the machinery of the stack visible, the actual recursive structure of the algorithm is a lot less clear to many people. Note that I say "many people" - some people naturally understand recursion and some don't. (I used to teach Scheme and Prolog to freshmen, and I'd say that very roughly a third of them do and two thirds don't.) Entire books have been written just to get the latter kind of students over this hurdle, and since you seem to belong to the former kind, I don't know if I can convey to you how mystifying the concept is to many people. It isn't even a question of understanding the sequence of steps that happens, more an issue of believing that it is possible to use a definition that seems to be not yet complete. The solution involves lots of practice and lots of stepping through some small and medium-size examples. Eventually this will let the penny drop for many learners, although by far not all.

Answer 3

LKM simply means a manually handled stack, for example a linked list where you push elements at the head and then pop them out again. It'd be faster because it's smaller, less data to shuffle around.

It's implemented by having a field in your struct that's a pointer (or reference if you wish) to the next element, and a head variable that's the top of the stack. When you push, you set the next pointer of your pushed element to the current value of the head variable, and then set the head variable to reference the pushed element. Popping does the inverse.

Another way to implement it, if you know the maximum stack of the stack, is to have a normal array and an index variable which tells where in the array the head is. That's actually how the recursion call stack is implemented, if you simplify it.

I believe most of the languages you mention above also have special constructs to treat arrays as stacks, usually called push/pop or shift/unshift.