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

Groups > comp.lang.c > #154672

Re: An experimental max_n for int's...

Show all headers | View raw

antispam@math.uni.wroc.pl writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> I write small recursive functions like this all the time.  My
>> experience is that compilers are almost always smart enough to
>> turn tail-call recursion into loops, like what was done in the
>> two compilations shown above.  Of course it is possible, if a
>> naive compiler is used or if optimization settings are too low,
>> that the tail-call optimization won't happen, and truly recursive
>> object code will be the result.  Usually though that doesn't
>> happen.  If we are being careful -- and we should be -- the lack
>> of actual recursion in the object code should be verified;  after
>> all, we don't want any nasty surprises.  But this isn't hard to
>> do.  It's a fairly simple matter to write a program in the
>> scripting language of your choice (I used awk) that can scan code
>> in this format and report cases of recursive calls in the object
>> code.  Having the tool in hand, making use of tail calls and tail
>> recursion can be done with confidence.
>>
>> I recommend developing an ability to write simple functions like
>> this using a recursive, tail-call-optimizable, style.  Once you
>> get the knack I think you will find it quite empowering.
>
> Well, it is good to know how to write tail-call-optimizable
> functions when you must.  However, I would discourage such
> style:
>
> - to make code tail-call-optimizable may require unnatural

The style is unnatural to you because you aren't used to it.
Perhaps the main point of my suggestion is that there is nothing
inherently unnatural about it, and it is only lack of familiarity
that might make it seem so.

>   transformations

I think you're implicitly suggesting that the code is imagined
first in an iterative formulation, and then is "transformed", to
use your word, into a functional style.  When someone is starting
to go up this particular learning curve certainly that could
happen (it did for me).  However, once you get used to it, there
are no transformations:  the very first writing is expressed in a
functional style, with no iterative version having been imagined.
I find it easier and faster (in many although not all cases, in
case that needs saying) to write a functional form than an
iterative form, and the functional form is the first and only way
the code gets expressed.

>   and extra variables which are not needed
>   in iterative version

The recursive version here uses fewer variables than the
iterative version, because no loop index is needed.  I think that
is also true in many other cases, because no loop variable is
needed when the code is written functionally.

> - main power of recursion comes from stack (or whatever is
>   used to handle recursive calls).

I'm sure that is how many people are taught to think of
recursion, but that doesn't make it true.  In any case
the key attribute here is using a declarative/functional
style;  that recursion is used is mostly incidental.

>   If you are not going
>   to use full power of recursion, then using explicit
>   loop is more readible:

This again is the prejudice of your previous experience and
education.  I find the functional form easier to read, easier to
understand, and easier to confirm correct.  (Again that is true
in many though not all cases).

>   with explicit loop it is clear
>   that code is iterative, for tail-call-optimizable
>   functions you must carefully look at code to know
>   if code is optimizable

You may feel that way, but I don't, and I think people who take
the suggestions given won't either.  First recognizing when a
function call is a tail call is so simple as to be almost
effortless.  Second the question is not whether the code is
optimizable but whether the code has been optimized, and I
explained that this check can easily be automated.  I don't
have to look at whether tail calls were optimized for the
same reason I don't have to check whether variables are used
before being initialized:  I can reliably count on the tools
to do that for me.

> BTW:  Instead of tail-call-optimization I definitly prefer
> explicit "tail jump" at the end.  Unfortunately, languages
> which have such "tail jump" seem to be quite rare (of
> course "tail jump" is not available in standard C).

To me this seems backwards.  A large part of the motivation for
programming in a high level language (and I count C as being
among those) is not to have to think in assembly language.
Needing to distinguish between a "tail call" and a "tail jump" is
like being forced to work in assembly language again.  Working at
the machine level is useful now and then, but certainly not all
the time.

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

Thread

Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:01 -0700
  Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-30 03:35 -0700
    Re: An experimental max_n for int's... Bart <bc@freeuk.com> - 2020-08-30 12:12 +0100
      Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 20:33 -0700
        Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-31 07:50 -0400
          Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-31 17:46 -0700
            Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 02:32 +0100
              Re: An experimental max_n for int's... Richard Damon <Richard@Damon-Family.org> - 2020-09-01 07:27 -0400
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 13:36 +0100
                Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-09-01 10:21 -0400
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 15:57 +0100
                Re: An experimental max_n for int's... Richard Damon <Richard@Damon-Family.org> - 2020-09-01 21:45 -0400
                Re: An experimental max_n for int's... David Brown <david.brown@hesbynett.no> - 2020-09-01 14:39 +0200
                Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-09-01 10:28 -0400
      Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-09-07 08:28 -0700
    Re: An experimental max_n for int's... antispam@math.uni.wroc.pl - 2020-08-30 12:37 +0000
      Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-09-07 08:18 -0700

csiph-web