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

Groups > comp.lang.c > #54894

Re: C-Programming

Show all headers | View raw

Richard Heathfield <invalid@see.sig.invalid> writes:

> JohnF wrote:
>
>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>> <<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). <<snip>>
>> 
>> Various algorithms, like generating bezier curves and some fractals,
>> are naturally recursive -- pretty easy to express and code recursively,
>> and will pretty much drive you crazy if you try to think it through
>> and code it iteratively, regardless of language.
>
> Some fractals, I'd agree with. Bezier curves, though? It never even occurred 
> to me to draw these recursively, and I didn't have any particular difficulty 
> with the iterative method. Am I doing something wrong?

I am sure you are not doing anything wrong, but there are other ways.

The usual recursive solution comes in two flavours both, based on what's
called De Casteljau's algorithm.  In one flavour you use this
numerically, but the prettiest version is a direct geometric realisation
of it.  To

  draw_curve(p1, c1, c2, p2);

(that's the curve from p1 to p2 using c1 and c2 as control points) you
calculate 6 mid-points and draw two smaller curves:

  p1c1 = mid(p1, c1);
  c1c2 = mid(c1, c2);
  c2p2 = mid(c2, p2);
  p1c1c1c2 = mid(p1c1, c1c2);
  c1c2c2p2 = mid(c1c2, c2p2);
  m = mid(p1c1c1c2, c1c2c2p2);

  draw_curve(p1, p1c1, p1c1c1c2, m);
  draw_curve(m, c1c2c2p2, c2p2, p2);

To see what's happening, draw the lines p1-c1, c1-c2 and c2-p2.  Now
draw lines between the mid-points of each consecutive pair of these
lines.  Then do the same between the mid-points of every consecutive
pair you now have... and so on.  (If you are like me, you need to draw
it to see what's happening but it's just the high-tech version of the
art with string and nails that I remember doing at school.)

The recursion stops (and you draw a line) when some metric becomes small
enough.  You can use a recursion count, some measure of the distance
between the end points, or some measure of the "bend" in the curve (or
some combination of these, of course).

-- 
Ben.

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

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