[LLVMdev] Does LLVM optimize recursive call?

[Sean Silva]

> Only if the recursion is very deep. In practice, a recursive descent
> parser isn't going to run out of stack space, nor will a quicksort or
> binary-tree walker,

The recursive-descent parser case has happened in practice:
http://my.opera.com/hallvors/blog/2012/07/17/twitter-crashes-itself-with-commas?1

Also, I've seen some recursion-related PR's in Clang, although I think
that they are usually related to templates and not parsing.

Also, it's easy to blow stack in quicksort if you don't tail call into
the recursive invocation of the _larger_ subrange. Recursively calling
into the smaller subrange guarantees that it's size is less than half
of the current range, whereas a non-tail call into the larger subrange
can require linear stack space if the partition isn't good.

> You're distracting this man from his job of learning how to program.

Indeed. Journeyer, you should ignore this stuff that we are saying,
these are all exceptions: you'll fix them if they arise, but you
generally shouldn't design with them in mind. Journeyer, if you want
to learn more about tail calls, I recommend this paper by Guy Lewis
Steele, Jr.:
http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf
It's a pretty old paper, but it is exactly about your original
question. By the end, you'll probably know more about tail calls as
you'll ever need to know :)

-- Sean Silva

On Wed, Oct 3, 2012 at 1:28 PM, Preston Briggs <preston.briggs at gmail.com> wrote:
> On Wed, Oct 3, 2012 at 10:15 AM, Matthieu Moy
> <Matthieu.Moy at grenoble-inp.fr> wrote:
>> Preston Briggs <preston.briggs at gmail.com> writes:
>>> Think about costs asymptotically; that's what matters. Calls and
>>> returns require constant time, just like addition and multiplication.
>>
>> Constant time, but not necessarily constant memory.
>>
>> Deep recursion will blow up your stack (AKA "segmentation fault" :-( )
>> if the compiler could not optimize it (tail recursion optimization).
>
> Only if the recursion is very deep. In practice, a recursive descent
> parser isn't going to run out of stack space, nor will a quicksort or
> binary-tree walker,
>
> You're distracting this man from his job of learning how to program.
>
> Yes, it's a mistake to have a set of mutually recursive routines that
> chew up all your stack space; but it's a mistake to reply on a
> compiler optimization to avoid such problems. Write an explicit loop
> if it's a possibility.
>
> Preston
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev