Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?
share|improve this question
    
I don't see any comments on that page by "LKM". A text search turns up one comment by "blkmage" and one response to his comment, but that's it. –  Mason Wheeler Nov 4 '11 at 21:32
    
@Mason I found the comments searching for "LKM". –  JGWeissman Nov 4 '11 at 21:37
    
Oh, nevermind. My mistake. –  Mason Wheeler Nov 4 '11 at 21:40
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
1  
I don't understand the benefit of this. Whats wrong with using the call stack (other than stack overflows)? –  Pubby Nov 4 '11 at 21:38
    
@Pubby Often there is no benefit, especially if you are using a functional language with compiler optimizations related to recursion. If you are using a language like javascript, there can be performance benefits, though beware premature optimizations. An explicit stack can also be more elegant in some ways, a depth first traversal of a tree using an explicit stack can be changed into a breadth first traversal be replacing the stack with a queue. –  JGWeissman Nov 4 '11 at 21:49
1  
For one thing, your heap (if you heap allocate the explicit stack) is a lot bigger than the call stack. So you can go deeper. Also if you bothered to rewrite a recursive algorithm into an iterative one with an explicit stack, you are often close enough so that with a minimum of additional effort you can manually wring out the tail-call optimization. At that point you win. –  Lambdageek Nov 5 '11 at 1:01
add comment

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.

share|improve this answer
2  
How the hell is a linked list faster than a hardware call stack? –  Pubby Nov 4 '11 at 21:40
    
Well, it isn't necessarily, but it might be. If there's a stack frame that needs to be setup, and registers saved on the stack, then it most likely is. –  Per Johansson Nov 4 '11 at 21:46
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.