Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #67485

Re: Why does this work on Xcode ???

Show key headers only | View raw

Christian Gollwitzer <auriocus@gmx.de> writes:

> Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:
>
>> On 17.07.2019 23:15, Mr Flibble wrote:
>>
>>> The whole point of using tail recursion is that is doesn't use
>>> up stack space, silly boy.
>>
>> Unfortunately the C++ standard gives you no such guarantee.
>>
>> But a particular compiler may.
>>
>> It's difficult to predict because it may not be documented for
>> the compiler, and the compiler may optimize or not based on
>> criteria that only make sense internally (e.g., is the return
>> type floating point?).
>
> Is it true that it depends on the type of something in practical
> cases?

The short answer is yes.  (more below)

> I thought that tail recursion can be mechanically translated
> like this:
>
> ===========
> type myfunc(x, y, z) {
>     ....
>
>     return myFunc(a, b, c);
> }
> ===========
>
> becomes
>
> ==========
> type myfunc(x, y, z) {
>     start:
>
>     ...
>
>     x=a, y=b, z=c;
>     goto start;
>
> }
> ==========
>
> Since I can do this at the source code level, I don't see why it
> can't be done for every function.  Of course, for mutual tail
> recursion I can't do that because of the non-local goto, but for
> the compiler that should also be easy.

I switch pretty easily (in C or C++) between functional style
code and imperative style code.  So I routinely write small
functions using self-recursion, or sometimes mutual recursion
although that is less common.  Of course I also want my code
to be practical so I do look at how the code is compiled,
sometimes with a visual inspection and sometimes using a
filter on the generated assembly to see where tail recursion
is compiled "badly", as a recursive call, rather than being
turned into a loop.

My experience is that direct tail recursion almost always[*] gets
turned into loops rather than recursive calls, if all the types
involved are scalar types (or references in C++).  That also
holds for mutual recursion in cases where the functions involved
all have the same type (that is, the same return type and also
the same argument types, or at least "similar" argument types).
When the functions involved in a mutual recursion have different
numbers of arguments the results are not as reliable.

An important case that does *not* get compiled as iterative code
is when the return type is a struct (which I think also includes
unions).  For some reason that happens even when the struct is
"simple", such as having only one member (and which has scalar
type).  In C, using struct types for arguments is usually okay,
provided of course that they aren't too hairy.  In C++, using
struct types for arguments often inhibits getting iterative
compiled code, even for "plain" structs.  (Disclaimer:  I haven't
explored what goes on when struct argument types are involved,
or more accurately I haven't explored it too deeply.)

On the flip side, a C++ case where recursion works great is
when constexpr functions are used to calculate constexpr
values.  This property is important if one needs to write
constexpr functions that work in C++11 (and some people still
do), as in nearly all cases iterative code can be turned into
equivalent recursive code that adheres to the more restrictive
constraints for constexpr functions in C++11.


[*] Using gcc, clang, or g++, at optimization levels -Os/-O2 or
higher.  Also, all the foregoing statements should be read as
most often true but not as absolutely true - there are always
the odd corner cases that can pop up, as with all things
programming.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Why does this work on Xcode ??? Bob Langelaan <bobl0456@gmail.com> - 2019-07-16 22:03 -0700
  Re: Why does this work on Xcode ??? Paavo Helde <myfirstname@osa.pri.ee> - 2019-07-17 08:46 +0300
  Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 00:06 -0700
    Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 01:44 -0700
  Re: Why does this work on Xcode ??? Juha Nieminen <nospam@thanks.invalid> - 2019-07-17 07:46 +0000
  Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-07-17 09:12 -0400
  Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 17:01 +0200
    Re: Why does this work on Xcode ??? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-07-17 22:15 +0100
      Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 23:29 +0200
        Re: Why does this work on Xcode ??? Christian Gollwitzer <auriocus@gmx.de> - 2019-07-19 08:27 +0200
          Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:09 +0200
            Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:24 +0200
            Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 11:18 -0700
              Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-10 21:05 +0200
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-22 10:28 -0700
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-22 19:50 +0200
                Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-22 23:45 +0100
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 07:22 +0200
                Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-23 13:12 +0100
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 16:02 +0200
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-09-18 08:50 -0700
                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 09:28 -0400
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-23 16:37 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 23:07 +0200
                Re: Why does this work on Xcode ??? Richard Damon <Richard@Damon-Family.org> - 2019-08-23 19:10 -0400
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:49 +0200
                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 19:49 -0400
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:45 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 12:06 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:25 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:11 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 17:12 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 23:32 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-26 11:51 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-26 13:26 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 11:36 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:27 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:15 +0200
                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-26 00:43 -0400
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-24 04:58 -0700
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-26 09:53 -0700
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-28 18:03 -0700
          Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-19 00:20 -0700
          Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-09 07:41 -0700
      Re: Why does this work on Xcode ??? Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-24 19:49 +0200
    Re: Why does this work on Xcode ??? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-07-21 11:41 +0000
      Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 09:29 -0700

csiph-web