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

Ron Garret ron at flownet.com
Sun Aug 28 03:10:00 EDT 2016


On Aug 27, 2016, at 8:37 AM, John Levine <johnl at iecc.com> wrote:

>> |  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.

If you want to argue that C is “a good portable assembler” (which is the claim I was responding to) then these sorts of things matter.  You should not have to determine whether or not your code is going to blow the stack by disassembling the output of your assembler.

rg



More information about the cryptography mailing list