[Cryptography] tail recursion in C [was Re: "NSA-linked Cisco exploit poses bigger threat than previously thought"]

John Levine johnl at iecc.com
Sat Aug 27 11:37:31 EDT 2016


>|  You can't GOTO a label outside of the current function.  That 
>| makes it impossible to implement tail recursion in pure C unless you 
>| compile your entire program into a single C function.
>
>If the last act of a function is to call another function, that call
>can be compiled as a goto (plus some conversion of the current
>function's activation record into the parameters for the new
>function).  Tail recursion optimization is a special case of this.
>
>This is purely an implementation feature.  I cannot think of anything
>in C that precludes this optimization.  Just culture?

GCC and clang will often optimize tail calls into jumps, even fiddling
the stack frames if the two routines don't have the same argument
sizes.  (I just checked).

A lot of C programmers don't know that or don't trust their particular
compiler to do it, so they still code as though tail calls are
expensive.

I have to say I don't see this as a big deal.  If your routines are so
small that the call/return overhead is a problem, most of them should
be inlined or macros anyway.  Of course, C compilers often optimize
calls by inlining them, too.  I wrote a little test program with two
mutually tail recursive calls and it compiled them into a loop.

R's,
John





More information about the cryptography mailing list