Re: C-Programming

From	Tim Rentsch <txr@alumni.caltech.edu>
Newsgroups	comp.lang.c
Subject	Re: C-Programming
Date	2014-12-16 18:23 -0800
Organization	A noiseless patient Spider
Message-ID	<kfnsigf815a.fsf@x-alumni2.alumni.caltech.edu> (permalink)
References	(1 earlier) <m62r3k$joh$1@dont-email.me> <kfnbnn3bw76.fsf@x-alumni2.alumni.caltech.edu> <m6pe1r$v14$1@dont-email.me> <kfnegrz9kyf.fsf@x-alumni2.alumni.caltech.edu> <m6qlks$6c6$1@dont-email.me>

Show all headers | View raw

David Brown <david.brown@hesbynett.no> writes:

> On 17/12/14 01:30, Tim Rentsch wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 16/12/14 13:44, Tim Rentsch wrote:
>>>> David Brown <david.brown@hesbynett.no> writes:
>>>>
>>>>> On 06/12/14 20:09, arvindgupta01031988@gmail.com wrote:
>>>>>> How to use a recursive function in C ?
>>> [snip]
>>
>> As for recursive implementations in C having no practical utility,
>> that may be true for factorial, but it certainly is not true for
>> other uses.  In particular, for Fibonacci numbers, the fastest
>> implementation in C I have seen used a recursive definition (ie,
>> the C code was itself recursive).  Also, even if a recursively
>> defined factorial would not be a likely choice when implementing
>> in C, the example of factorial could still be useful, to point
>> out the difference between an "iterable" version that uses tail
>> recursion and a "non-iterable" version that does not, which you
>> seem to be familiar with.  None of the examples besides my own
>> illustrated function definitions that used tail recursion.
>
> The factorial function can be conveniently written recursively,
> as long as you are happy that your compiler will turn it into
> iterative object code - otherwise an iterative implementation
> will be much faster.

The point of my comment was not about factorial but how to
write recursive functions effectively.  A straightforward
implementation of factorial that uses recursion will not be
optimized by any compiler into a loop (ignoring ones that
have some sort of special casing), because it does not
use tail recursion.  I hope you're not lumping together
all function definitions that use simple recursion, for
they certainly are not treated equally by optimizing compilers --
and this would be good for people to know.

> For Fibonacci numbers, any program that actually needs the values
> will use direct calculation from powers of phi, as it is smaller
> and faster than recursive or iterative calculations.

Not so.  The recursive version I posted here not long ago
is both faster and more accurate than direct calculation
using powers of phi.

> But there are certainly many other algorithms that can be best
> expressed recursively.  In particular, many searching, sorting
> and tree algorithms are neatest and clearest when written
> recursively.

Many simple algorithms commonly written using iteration can be
written more succinctly and IMO more obviously correct using
recursion, with performance approximately the same (sometimes a
little worse, sometimes a little better).  The only reason more
people don't do that is because iteration is what they're used to,
not for any solid technical reason.  The best way to get people to
understand both the pros and cons of recursion is to illustrate
using simple algorithms, not to limit the discussion to more
sophisticated algorithms such as the ones you mention.

Thread

C-Programming arvindgupta01031988@gmail.com - 2014-12-06 11:09 -0800
  Re: C-Programming "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2014-12-06 11:16 -0800
  Re: C-Programming James Kuyper <jameskuyper@verizon.net> - 2014-12-06 14:46 -0500
    Re: C-Programming Kleuske <kleuske@nowhere.net> - 2014-12-07 10:48 +0000
      Re: C-Programming Keith Thompson <kst-u@mib.org> - 2014-12-07 07:43 -0800
  Re: C-Programming Siri Crews <chine.bleu@yahoo.com> - 2014-12-06 12:22 -0800
    Re: C-Programming gordonb.ukogy@burditt.org (Gordon Burditt) - 2014-12-19 03:29 -0600
      Re: C-Programming Siri Crews <chine.bleu@yahoo.com> - 2014-12-19 01:34 -0800
        Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-19 10:18 +0000
          Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-19 17:42 +0100
            Re: C-Programming rouben@shadow.(none) (Rouben Rostamian) - 2014-12-19 19:00 +0000
              Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-19 20:31 +0100
                Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-19 20:42 +0100
              Re: C-Programming Keith Thompson <kst-u@mib.org> - 2014-12-19 11:54 -0800
        Re: C-Programming raltbos@xs4all.nl (Richard Bos) - 2014-12-19 11:29 +0000
          Re: C-Programming Noob <root@127.0.0.1> - 2014-12-20 10:22 +0100
            Re: C-Programming Keith Thompson <kst-u@mib.org> - 2014-12-20 11:48 -0800
        Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-19 03:33 -0800
          Re: C-Programming Siri Crews <chine.bleu@yahoo.com> - 2014-12-19 04:02 -0800
      Re: C-Programming glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-12-19 17:28 +0000
  Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-06 21:27 +0100
  Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-07 13:07 +0000
  Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-08 01:24 +0100
    Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-16 04:44 -0800
      Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-16 15:02 +0100
        Re: C-Programming BartC <bc@freeuk.com> - 2014-12-16 18:27 +0000
          Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-17 01:01 +0100
            Re: C-Programming BartC <bc@freeuk.com> - 2014-12-17 00:23 +0000
        Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-16 16:30 -0800
          Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-17 02:18 +0100
            Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-16 18:23 -0800
              Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-17 09:59 +0100
                Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-17 08:52 -0800
                Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-18 11:11 +0100
                Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-18 09:49 -0800
          Re: C-Programming JohnF <john@please.see.sig.for.email.com> - 2014-12-17 10:14 +0000
            Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-17 14:26 +0000
              Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-17 09:13 -0800
                Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-17 17:34 +0000
                Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-17 23:26 -0800
                Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-18 00:21 -0800
                Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-18 17:06 +0000
                Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-18 09:29 -0800
                Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-19 02:36 +0000
                Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-19 03:41 -0800
                Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-18 08:52 -0800
              Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-17 23:23 +0000
                Re: C-Programming BartC <bc@freeuk.com> - 2014-12-18 00:02 +0000
                Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-18 00:15 +0000
                Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-18 16:37 +0000
                Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-18 18:08 +0000
                Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-19 02:40 +0000
                Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-19 07:51 +0000
            Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-17 09:07 -0800
              Re: C-Programming JohnF <john@please.see.sig.for.email.com> - 2014-12-19 04:22 +0000
                Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-19 09:22 -0800
                Re: C-Programming Greg Martin <greg.at.softsprocket@dot.com> - 2014-12-20 02:39 +0000
                Re: C-Programming JohnF <john@please.see.sig.for.email.com> - 2014-12-20 06:57 +0000
  Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-15 23:53 -0800

csiph-web