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

Groups > comp.lang.c > #53998 > unrolled thread

C-Programming

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#54002

Le 06/12/2014 20:09, arvindgupta01031988@gmail.com a écrit :
> How to use a recursive function in C ?
>

   1 #include <stdio.h>
   2 int main(int argc, char *argv[])
   3 {
   4     int r;
   5     printf("--> %d\n",argc);
   6     if (argc< 1)
   7         return 0;
   8     r = 1+main(argc-1,argv);
   9     printf("%d <--\n",r);
  10     return r;
  11 }

/tmp $ ./a.out 1 2 3 4 5 6 7 8
--> 9
--> 8
--> 7
--> 6
--> 5
--> 4
--> 3
--> 2
--> 1
--> 0
1 <--
2 <--
3 <--
4 <--
5 <--
6 <--
7 <--
8 <--
9 <--

1: Include needed for printf
2: This is the minimum for a C program: a function called "main"
3: The single scope
4: The result of main in this example is an integer "r" for result.
5: Going inside the recursion arrow towards the right
6: Stopping condition of the recursion
7: Result at the bottom
8: Recursion
9: Going outside arrow is to the left.
10. Done

[toc] | [prev] | [next] | [standalone]

#54038

arvindgupta01031988@gmail.com writes:

> How to use a recursive function in C ?

The best way to find out is to write programs to solve problems where
there is a reasonably "natural" recursive solution.  Here are a few
ideas that, with luck, don't rely on data structures you may not yet
have learned about.

Binary search.  Given a sorted array of numbers (let's say ints for now)
find out if a given number is in the list.  I.e. write

  bool contains(int n, const int *numbers, size_t how_many);

Making change.  Given a sorted array of coin denominations, count how
many ways there are to make up a given quantity.  For example, in the UK
with coin denominations of 1, 2, 5, 10, 20, 50, 100 and 200 (pence)
there are 73,682 ways to make 2 pounds (200 pence).

Variation: print the different ways.

Variation: do the same thing but limited by the number of coins of each
denomination that are available.

Permutations.  Print all the permutations of a string.  I.e. write a
function print_perms so that so that print_perms("abc") prints

  abc
  acb
  bac
  bca
  cab
  cba

in some order of your choosing.

Eight queens.  How many ways are there of placing 8 queens on an 8x8
chess board so that no two are attacking each other (i.e. no two are on
the same row, column or diagonal)?

Variation: what about N queens on and NxN chess board?

All of these can be written without recursion, and sometimes that
natural recursive solution is far from the most efficient, but they do
give you a way into thinking about breaking a problem up identical
sub-problems with is, in essence, what recursion allows you to do.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#54054

On 06/12/14 20:09, arvindgupta01031988@gmail.com wrote:
> How to use a recursive function in C ?
>

unsigned int ackermann(unsigned int m, unsigned int n) {
	if (m == 0) return n + 1;
	if (n == 0) return ackermann(m - 1, 1);
	return ackermann(m - 1, ackermann(m, n - 1));
}

That is recursive, and it is unlikely that your compiler will turn it 
into a non-recursive implementation.  Just don't call it with m > 3.

[toc] | [prev] | [next] | [standalone]

#54679

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 ?
>>
>
> unsigned int ackermann(unsigned int m, unsigned int n) {
> 	if (m == 0) return n + 1;
> 	if (n == 0) return ackermann(m - 1, 1);
> 	return ackermann(m - 1, ackermann(m, n - 1));
> }
>
> That is recursive, and it is unlikely that your compiler will turn
> it into a non-recursive implementation. 

That's true for an obvious reason (because one of the calls is
not tail recursive), but also more definitely for a less obvious
reason - the function this C code is meant to represent is not
primitive recursive, and so is theoretically impossible to turn
into an iterative solution (in the normal sense of the word
iterative).  Moreover it has no practical utility, unlike for
example factorials or (in some situations) fibonacci numbers.
Another useful function is greatest common divisor, which has a
very nice recursive solution.  I think any of those would have
been a better example for someone interested in learning about
recursion in C.

[toc] | [prev] | [next] | [standalone]

#54696

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 ?
>>>
>>
>> unsigned int ackermann(unsigned int m, unsigned int n) {
>> 	if (m == 0) return n + 1;
>> 	if (n == 0) return ackermann(m - 1, 1);
>> 	return ackermann(m - 1, ackermann(m, n - 1));
>> }
>>
>> That is recursive, and it is unlikely that your compiler will turn
>> it into a non-recursive implementation. 
> 
> That's true for an obvious reason (because one of the calls is
> not tail recursive), but also more definitely for a less obvious
> reason - the function this C code is meant to represent is not
> primitive recursive, and so is theoretically impossible to turn
> into an iterative solution (in the normal sense of the word
> iterative).  Moreover it has no practical utility, unlike for
> example factorials or (in some situations) fibonacci numbers.
> Another useful function is greatest common divisor, which has a
> very nice recursive solution.  I think any of those would have
> been a better example for someone interested in learning about
> recursion in C.
> 

The OP had received plenty of examples of useful recursive functions,
including the obvious beginners choices of factorials and binary search.
 So I was looking at an example that is more interesting, since it is
not a primitive recursive function.  It is true that it is of no
practical utility - but neither is a recursive implementation of
factorials or Fibonacci numbers (except perhaps when you are using a
functional programming language rather than C).

So looking at the theory here, clearly I agree that the Ackermann
function can't be turned into a simple loop.  Equally clearly, it can be
turned into an iterative solution with a stack structure (simulating the
recursion).  But is it possible to get a better iterative implementation
- or does the non-primitive recursive nature rule that out?  It is a
long time since I have studied such things, and while I /might/ be able
to recall the proof that the function is not primitive recursive, I
don't know anything about alternative implementations.

[toc] | [prev] | [next] | [standalone]

#54726

On 16/12/2014 14:02, David Brown wrote:
> On 16/12/14 13:44, Tim Rentsch wrote:

[Ackermann functions]

>> Moreover it has no practical utility, unlike for
>> example factorials or (in some situations) fibonacci numbers.

> It is true that it is of no
> practical utility - but neither is a recursive implementation of
> factorials or Fibonacci numbers

It has a use in benchmarking. Also in testing deep recursion.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#54782

On 16/12/14 19:27, BartC wrote:
> On 16/12/2014 14:02, David Brown wrote:
>> On 16/12/14 13:44, Tim Rentsch wrote:
>
> [Ackermann functions]
>
>>> Moreover it has no practical utility, unlike for
>>> example factorials or (in some situations) fibonacci numbers.
>
>> It is true that it is of no
>> practical utility - but neither is a recursive implementation of
>> factorials or Fibonacci numbers
>
> It has a use in benchmarking. Also in testing deep recursion.
>

You can't use a recursive implementation of factorials in benchmarking - 
an optimising compiler will turn it into an iterative loop, and there is 
no point in benchmarking without enabling optimisation.

[toc] | [prev] | [next] | [standalone]

#54787

On 17/12/2014 00:01, David Brown wrote:
> On 16/12/14 19:27, BartC wrote:
>> On 16/12/2014 14:02, David Brown wrote:
>>> On 16/12/14 13:44, Tim Rentsch wrote:
>>
>> [Ackermann functions]
>>
>>>> Moreover it has no practical utility, unlike for
>>>> example factorials or (in some situations) fibonacci numbers.
>>
>>> It is true that it is of no
>>> practical utility - but neither is a recursive implementation of
>>> factorials or Fibonacci numbers
>>
>> It has a use in benchmarking. Also in testing deep recursion.
>>
>
> You can't use a recursive implementation of factorials in benchmarking -
> an optimising compiler will turn it into an iterative loop, and there is
> no point in benchmarking without enabling optimisation.
>
That might not matter, if the optimisation technique is fair.

I was however talking about an Ackermann benchmark, and gcc -O3 actually 
does a better job of optimising that than a Fibonacci one!

(Ackermann is about 5 times faster than my compiler, and Fibonacci 
double. But with -O0, the programs run a bit slower than mine (which 
does have some simple optimisations, but nothing that's useful here).)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#54791

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 ?
>>>>
>>>
>>> unsigned int ackermann(unsigned int m, unsigned int n) {
>>> 	if (m == 0) return n + 1;
>>> 	if (n == 0) return ackermann(m - 1, 1);
>>> 	return ackermann(m - 1, ackermann(m, n - 1));
>>> }
>>>
>>> That is recursive, and it is unlikely that your compiler will turn
>>> it into a non-recursive implementation. 
>> 
>> That's true for an obvious reason (because one of the calls is
>> not tail recursive), but also more definitely for a less obvious
>> reason - the function this C code is meant to represent is not
>> primitive recursive, and so is theoretically impossible to turn
>> into an iterative solution (in the normal sense of the word
>> iterative).  Moreover it has no practical utility, unlike for
>> example factorials or (in some situations) fibonacci numbers.
>> Another useful function is greatest common divisor, which has a
>> very nice recursive solution.  I think any of those would have
>> been a better example for someone interested in learning about
>> recursion in C.
>> 
>
> The OP had received plenty of examples of useful recursive
> functions, including the obvious beginners choices of factorials
> and binary search.  So I was looking at an example that is more
> interesting, since it is not a primitive recursive function.

My sense is that the OP was looking for how to do recursion in C,
not for information about recursive functions.  The two topics
don't really have much in common.  Anyway that was my take on the
situation, and what prompted my comment.

> It is true that it is of no practical utility - but neither is a
> recursive implementation of factorials or Fibonacci numbers
> (except perhaps when you are using a functional programming
> language rather than C).

My point of my comment was about the function itself, not about how
it was implemented.  Both factorials and Fibonacci numbers,
considered purely as mathematical entitiess, have practical utility.
The Ackermann function does not.

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.

> So looking at the theory here, clearly I agree that the Ackermann
> function can't be turned into a simple loop.  Equally clearly, it
> can be turned into an iterative solution with a stack structure
> (simulating the recursion).  But is it possible to get a better
> iterative implementation - or does the non-primitive recursive
> nature rule that out?  It is a long time since I have studied such
> things, and while I /might/ be able to recall the proof that the
> function is not primitive recursive, I don't know anything about
> alternative implementations.

I believe the key point is that it cannot be implemented using
only O( 1 ) variables.  If that were so, and assuming the
successive values were monotonic in some sense, then I think that
could be mapped onto some primitive recursive function.  Because
we know that what we're dealing with is not primitive recursive,
this cannot be so.  A bit more concretely, functions like
Ackermann's function grow more rapidly than any primitive
recursive function, which I believe includes the complexity class
PSPACE.  So any implementation would need at least exponentially
much space allocated, which pretty much rules out any sort of
simple iterative method.

[toc] | [prev] | [next] | [standalone]

#54795

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 ?
>>>>>
>>>>
>>>> unsigned int ackermann(unsigned int m, unsigned int n) {
>>>> 	if (m == 0) return n + 1;
>>>> 	if (n == 0) return ackermann(m - 1, 1);
>>>> 	return ackermann(m - 1, ackermann(m, n - 1));
>>>> }
>>>>
>>>> That is recursive, and it is unlikely that your compiler will turn
>>>> it into a non-recursive implementation.
>>>
>>> That's true for an obvious reason (because one of the calls is
>>> not tail recursive), but also more definitely for a less obvious
>>> reason - the function this C code is meant to represent is not
>>> primitive recursive, and so is theoretically impossible to turn
>>> into an iterative solution (in the normal sense of the word
>>> iterative).  Moreover it has no practical utility, unlike for
>>> example factorials or (in some situations) fibonacci numbers.
>>> Another useful function is greatest common divisor, which has a
>>> very nice recursive solution.  I think any of those would have
>>> been a better example for someone interested in learning about
>>> recursion in C.
>>>
>>
>> The OP had received plenty of examples of useful recursive
>> functions, including the obvious beginners choices of factorials
>> and binary search.  So I was looking at an example that is more
>> interesting, since it is not a primitive recursive function.
>
> My sense is that the OP was looking for how to do recursion in C,
> not for information about recursive functions.  The two topics
> don't really have much in common.  Anyway that was my take on the
> situation, and what prompted my comment.

Yes, I know what the OP was asking for - but since his question had been 
answered (he has not responded), I thought this was an interesting 
side-track.  Arguably it could have been a new thread - but sidetracking 
existing threads is the c.l.c. tradition!

>
>> It is true that it is of no practical utility - but neither is a
>> recursive implementation of factorials or Fibonacci numbers
>> (except perhaps when you are using a functional programming
>> language rather than C).
>
> My point of my comment was about the function itself, not about how
> it was implemented.  Both factorials and Fibonacci numbers,
> considered purely as mathematical entitiess, have practical utility.
> The Ackermann function does not.

Yes - the Ackermann function is only of interest in computability 
theory, as an example of a computable function that is not primitive 
recursive.

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

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.

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.

>
>> So looking at the theory here, clearly I agree that the Ackermann
>> function can't be turned into a simple loop.  Equally clearly, it
>> can be turned into an iterative solution with a stack structure
>> (simulating the recursion).  But is it possible to get a better
>> iterative implementation - or does the non-primitive recursive
>> nature rule that out?  It is a long time since I have studied such
>> things, and while I /might/ be able to recall the proof that the
>> function is not primitive recursive, I don't know anything about
>> alternative implementations.
>
> I believe the key point is that it cannot be implemented using
> only O( 1 ) variables.

That could well be the key point, although I think it may be that it 
cannot be implemented using O(f(n)) variables where f is a polynomial - 
as you say later, it needs at least exponential space.  (Normal 
recursive functions can quickly require O(n) space, while still being 
primitive recursive.)

> If that were so, and assuming the
> successive values were monotonic in some sense, then I think that
> could be mapped onto some primitive recursive function.  Because
> we know that what we're dealing with is not primitive recursive,
> this cannot be so.  A bit more concretely, functions like
> Ackermann's function grow more rapidly than any primitive
> recursive function, which I believe includes the complexity class
> PSPACE.  So any implementation would need at least exponentially
> much space allocated, which pretty much rules out any sort of
> simple iterative method.
>

[toc] | [prev] | [next] | [standalone]

#54798

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.

[toc] | [prev] | [next] | [standalone]

#54809

On 17/12/14 03:23, Tim Rentsch wrote:
> 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.  

Note that the O/P has not made another post since his original post - he
has either got an answer that satisfied him, or has forgotten entirely
about the posting.  Either way, any posts in this thread are now mainly
for the entertainment (and occasionally education) of the c.l.c regulars.

But of course I agree that your answer was more helpful than mine in
showing how recursion could be used.  The irony is the that I would
never have written "skip" and "scan" functions recursively as you did,
because usually I would not want recursive functions (I work mostly with
memory-constrained systems) - but having seen that gcc is quite happy to
implement scan/skip iteratively and efficiently, I may be more inclined
to use recursive functions in the future!

> 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 can think of two ways to write a recursive factorial function:

int fact1(int a) {
    if (a <= 1) return 1;
    return a * fact1(a - 1);
}

int fact2(int a) {
    if (a <= 1) return 1;
    return fact2(a - 1) * a;
}

I don't know which you count as "straightforward" (I would say both),
but even a somewhat older gcc 4.5 has no problem implementing these
iteratively.


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

No, I wasn't lumping them together - and I agree that it is good for
people to know that compilers will not turn any or all recursive
functions into iterative loops.

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

I don't remember the details, though this rings a bell.  But we should
probably avoid re-doing it here.

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

If the compiler can turn the recursive code into a loop, then
performance will usually be similar.  But if it has to keep the
recursion, then recursion will quickly be much slower on many systems as
large stack usage means slow memory.

> The only reason more
> people don't do that is because iteration is what they're used to,
> not for any solid technical reason.  

Doing what you are used to doing /is/ a solid technical reason - you are
likely to do the job better and with lower risks of errors in a style
you are familiar with.

People might benefit from getting familiar with recursive styles,
however - then it would be another useful tool in the box.

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

If your aim is to encourage recursive coding style, then I agree with
you.  That wasn't the aim of my post, however - so there is nothing to
disagree about here.

[toc] | [prev] | [next] | [standalone]

#54862

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

> On 17/12/14 03:23, Tim Rentsch wrote:
>> 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 ?
>>>>> [snipping a bit more ...]
>>>>
>> The point of my comment was not about factorial but how to
>> write recursive functions effectively.  
>
> The irony is the that I would never have written "skip" and "scan"
> functions recursively as you did, because usually I would not want
> recursive functions (I work mostly with memory-constrained
> systems) - but having seen that gcc is quite happy to implement
> scan/skip iteratively and efficiently, I may be more inclined to
> use recursive functions in the future!

That's good.

I should add here that I don't know if I _would_ write code for
this functionality using recursive skip()/scan() functions, but
what's important is that I _might_ write it that way.  The point
is to have another tool in the kit.

>> 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 can think of two ways to write a recursive factorial function:
>
> int fact1(int a) {
>     if (a <= 1) return 1;
>     return a * fact1(a - 1);
> }
>
> int fact2(int a) {
>     if (a <= 1) return 1;
>     return fact2(a - 1) * a;
> }
>
> I don't know which you count as "straightforward" (I would say
> both),

Me too.

> but even a somewhat older gcc 4.5 has no problem
> implementing these iteratively.

I observe (with a slightly later gcc) that it does, but this
looks like special casing.  For example, replacing '*' with '^'
causes gcc to revert to using "call" rather than looping, even
though that definition is just as amenable to the transformation
used with '*'.  On the other hand, if we write a two-argument
form of factorial

    int
    factorial_times( int n, int p ){
        if( n<1 ) return p;
        return  factorial_times( n-1, n*p );
    }

then gcc will generate iterative code even if '^' is used where
the '*' is used here.  (And we can define factorial(n) as a
static inline that does 'return factorial_times( n, 1 );'.)

>>> 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.
>
> I don't remember the details, though this rings a bell.  But we
> should probably avoid re-doing it here.

I don't think there is anything to re-do, as long as you accept
my reported correction as accurate.

>>> 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).  
>
> If the compiler can turn the recursive code into a loop, then
> performance will usually be similar.  But if it has to keep the
> recursion, then recursion will quickly be much slower on many
> systems as large stack usage means slow memory.

Right, my comment was meant to apply to particular recursive
formulations, not to using recursion in general.  Indeed one of
my main points is to get people to learn the difference between
"good" recursion and "bad" recursion, and not tar all uses of
recursion with the same brush.

>> The only reason more people don't do that is because iteration
>> is what they're used to, not for any solid technical reason.
>
> Doing what you are used to doing /is/ a solid technical reason -

That's nonsense.  It may be a good reason, but it is not a
technical reason.  There is no "people science".

> you are likely to do the job better and with lower risks of
> errors in a style you are familiar with.

I'm sure that is true for some people, but not for all.  More
importantly, you're conflating doing just the very next thing
with doing the next ten or twenty or a hundred things.  Your
statement is "fuzzy" - not quantitative, not precise, not backed
up by objective and controlled studies that try to measure the
effects we are interested in.  I hope you won't find it offensive
if I say you seem prone to such fuzziness (to be fair, in some
circumstances, not all).  In any case my comment is about long
term behavior, not just what course to choose for the very next
thing.

> People might benefit from getting familiar with recursive styles,
> however - then it would be another useful tool in the box.

Exactly.

>> 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.
>
> If your aim is to encourage recursive coding style, then I agree
> with you.  That wasn't the aim of my post, however - so there is
> nothing to disagree about here.

My hope is to educate people about when and how recursion might
be used effectively, to promote more capable programmers (like
you said, with more tools in their kits), to illustrate some
differences between different kinds of recursion, and to promote
acceptance of using recursion when if offers a reasonable
alternative way of writing some function definition(s).  (I won't
call it the "best" way because usually there is no way that is
best along all relevant axes.)  And my hope is to get people out
of the habit of automatically thinking in terms of iteration, a
kind of "when all you have is a for/while hammer, everything
looks like an iterative nail' situation - it's only when someone
is facile with both iterative and recursive methods that some
alternative -- and useful! -- approaches present themselves.

[toc] | [prev] | [next] | [standalone]

#54920

On 17/12/14 17:52, Tim Rentsch wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 17/12/14 03:23, Tim Rentsch wrote:
>>> 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 ?
>>>>>> [snipping a bit more ...]
>>>>>
>>> The point of my comment was not about factorial but how to
>>> write recursive functions effectively.  
>>
>> The irony is the that I would never have written "skip" and "scan"
>> functions recursively as you did, because usually I would not want
>> recursive functions (I work mostly with memory-constrained
>> systems) - but having seen that gcc is quite happy to implement
>> scan/skip iteratively and efficiently, I may be more inclined to
>> use recursive functions in the future!
> 
> That's good.
> 
> I should add here that I don't know if I _would_ write code for
> this functionality using recursive skip()/scan() functions, but
> what's important is that I _might_ write it that way.  The point
> is to have another tool in the kit.

Agreed.

> 
>>> 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 can think of two ways to write a recursive factorial function:
>>
>> int fact1(int a) {
>>     if (a <= 1) return 1;
>>     return a * fact1(a - 1);
>> }
>>
>> int fact2(int a) {
>>     if (a <= 1) return 1;
>>     return fact2(a - 1) * a;
>> }
>>
>> I don't know which you count as "straightforward" (I would say
>> both),
> 
> Me too.
> 
>> but even a somewhat older gcc 4.5 has no problem
>> implementing these iteratively.
> 
> I observe (with a slightly later gcc) that it does, but this
> looks like special casing.  For example, replacing '*' with '^'
> causes gcc to revert to using "call" rather than looping, even
> though that definition is just as amenable to the transformation
> used with '*'.  

That's an interesting observation.  With -O3 (on gcc 4.9 - I haven't
tested others), the "^" version is also implemented iteratively - so
something between -O2 and -O3 enables it.

> On the other hand, if we write a two-argument
> form of factorial
> 
>     int
>     factorial_times( int n, int p ){
>         if( n<1 ) return p;
>         return  factorial_times( n-1, n*p );
>     }
> 
> then gcc will generate iterative code even if '^' is used where
> the '*' is used here.  (And we can define factorial(n) as a
> static inline that does 'return factorial_times( n, 1 );'.)
> 

I guess this all means that gcc has scope for more development!

>>>> 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.
>>
>> I don't remember the details, though this rings a bell.  But we
>> should probably avoid re-doing it here.
> 
> I don't think there is anything to re-do, as long as you accept
> my reported correction as accurate.

With the proviso that I don't remember the details (algorithms, target
processors, ranges, etc.), then I am happy to accept that your recursive
version was faster for a reasonable choice of test.

> 
>>>> 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).  
>>
>> If the compiler can turn the recursive code into a loop, then
>> performance will usually be similar.  But if it has to keep the
>> recursion, then recursion will quickly be much slower on many
>> systems as large stack usage means slow memory.
> 
> Right, my comment was meant to apply to particular recursive
> formulations, not to using recursion in general.  Indeed one of
> my main points is to get people to learn the difference between
> "good" recursion and "bad" recursion, and not tar all uses of
> recursion with the same brush.

Fair enough.

> 
>>> The only reason more people don't do that is because iteration
>>> is what they're used to, not for any solid technical reason.
>>
>> Doing what you are used to doing /is/ a solid technical reason -
> 
> That's nonsense.  It may be a good reason, but it is not a
> technical reason.  There is no "people science".

Let's just agree that it is a solid reason (which does not necessarily
imply a /good/ reason), and skip the argument about when a reason is
"technical" or not.

> 
>> you are likely to do the job better and with lower risks of
>> errors in a style you are familiar with.
> 
> I'm sure that is true for some people, but not for all.  More
> importantly, you're conflating doing just the very next thing
> with doing the next ten or twenty or a hundred things.  Your
> statement is "fuzzy" - not quantitative, not precise, not backed
> up by objective and controlled studies that try to measure the
> effects we are interested in.  I hope you won't find it offensive
> if I say you seem prone to such fuzziness (to be fair, in some
> circumstances, not all).  In any case my comment is about long
> term behavior, not just what course to choose for the very next
> thing.

I think most discussions and comments in a group like this will be fuzzy
- we might be happy to spend a few minutes making generalised comments
on a newsgroup, but few of us have the time and energy to make proper
scientific studies before writing.  And most of us leave at least some
"obvious" issues unstated (even though "obvious" is in the eye of the
beholder).  /Obviously/ it is worth learning a new method or technique
if it can be reused many times, even though it may be better to use an
old, known technique in a single instance.

(And no offence was taken.)

> 
>> People might benefit from getting familiar with recursive styles,
>> however - then it would be another useful tool in the box.
> 
> Exactly.
> 
>>> 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.
>>
>> If your aim is to encourage recursive coding style, then I agree
>> with you.  That wasn't the aim of my post, however - so there is
>> nothing to disagree about here.
> 
> My hope is to educate people about when and how recursion might
> be used effectively, to promote more capable programmers (like
> you said, with more tools in their kits), to illustrate some
> differences between different kinds of recursion, and to promote
> acceptance of using recursion when if offers a reasonable
> alternative way of writing some function definition(s).  (I won't
> call it the "best" way because usually there is no way that is
> best along all relevant axes.)  And my hope is to get people out
> of the habit of automatically thinking in terms of iteration, a
> kind of "when all you have is a for/while hammer, everything
> looks like an iterative nail' situation - it's only when someone
> is facile with both iterative and recursive methods that some
> alternative -- and useful! -- approaches present themselves.
> 

[toc] | [prev] | [next] | [standalone]

#54975

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

> On 17/12/14 17:52, Tim Rentsch wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 17/12/14 03:23, Tim Rentsch wrote:
>>>> 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 ?
>>>>>>> [... la la la la ... snippus extremus ...]

Just noting we seem to be basically in agreement on
all the snipped portions.

>>> you are likely to do the job better and with lower risks of
>>> errors in a style you are familiar with.
>> 
>> I'm sure that is true for some people, but not for all.  More
>> importantly, you're conflating doing just the very next thing
>> with doing the next ten or twenty or a hundred things.  Your
>> statement is "fuzzy" - not quantitative, not precise, not backed
>> up by objective and controlled studies that try to measure the
>> effects we are interested in.  I hope you won't find it offensive
>> if I say you seem prone to such fuzziness (to be fair, in some
>> circumstances, not all).  In any case my comment is about long
>> term behavior, not just what course to choose for the very next
>> thing.
>
> I think most discussions and comments in a group like this will
> be fuzzy - we might be happy to spend a few minutes making
> generalised comments on a newsgroup, but few of us have the time
> and energy to make proper scientific studies before writing.
> And most of us leave at least some "obvious" issues unstated
> (even though "obvious" is in the eye of the beholder).

I can't agree with this.  There are lots of participants who
routinely make fuzzy statements, but there are also lots of
others who do not.  You don't need to do the research yourself
to reference it, and web searches can be done pretty quickly.
IME sloppy language and sloppy thought usually go hand-in-hand.

> /Obviously/ it is worth learning a new method or technique if it
> can be reused many times, even though it may be better to use an
> old, known technique in a single instance.

It's good to hear you say so;  your earlier comment made it seem
like you were discouraging these kinds of activities in the topic
that was being discussed, which apparently is at odds with what you
really believe.

> (And no offence was taken.)

Glad to hear that!

[toc] | [prev] | [next] | [standalone]

#54820

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.
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

[toc] | [prev] | [next] | [standalone]

#54840

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?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#54868

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?

There is a well-known technique (which I've forgotten) for taking
a set of four Bezier control points, and dividing it into two
sets of control points for the two "halves" of the Bezier curve.
Recurse until the control points are suitably co-linear (or close
together) that the "curve" can be drawn as a straight line.  A
simple definition, and one that automatically adapts as needed to
draw only those lines needed to represent the curve accurately.

[toc] | [prev] | [next] | [standalone]

#54872

Tim Rentsch wrote:

> 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?
> 
> There is a well-known technique (which I've forgotten) for taking
> a set of four Bezier control points, and dividing it into two
> sets of control points for the two "halves" of the Bezier curve.
> Recurse until the control points are suitably co-linear (or close
> together) that the "curve" can be drawn as a straight line.  A
> simple definition, and one that automatically adapts as needed to
> draw only those lines needed to represent the curve accurately.

Thank you. I wasn't aware of that. My Bezier-drawing function uses only two 
control points (I /was/ aware that you can use more, but two seemed to me to 
be a sufficiency for the time being), so that might explain why I hadn't 
looked any further than:

  for(v = 0.0; v <= 1.0; v += inc)
  {
    neg = 1.0 - v;

    xv = 1 * 1         * neg * neg * neg * x0 +
         3 * v         * neg * neg       * cpax +
         3 * v * v     * neg             * cpbx +
         1 * v * v * v * 1               * x1;
    yv = 1 * 1         * neg * neg * neg * y0 +
         3 * v         * neg * neg       * cpay +
         3 * v * v     * neg             * cpby +
         1 * v * v * v * 1               * y1;
    xi = xv;
    yi = yv;
    if(xi >= 0 && xi < fb->width &&
       yi >= 0 && yi < fb->height)
    {
      set_pixel(fb, xi, yi, colour);
    }
  }

The control points are (cpax, cpay) and (cpbx, cpby), in case it wasn't 
obvious.

It has, of course, become the tradition, when I post ancient code, for 
people to find a good half-dozen bugs in it. No doubt the same will happen 
here. But this code does draw splines, really it does. :-)

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#54908

On Wednesday, December 17, 2014 5:34:16 PM UTC, Richard Heathfield wrote:
> 
> Thank you. I wasn't aware of that. My Bezier-drawing function uses only 
> two control points (I /was/ aware that you can use more, but two seemed
> to me to be a sufficiency for the time being), 
>
> It has, of course, become the tradition, when I post ancient code, for 
> people to find a good half-dozen bugs in it. No doubt the same will happen 
> here. But this code does draw splines, really it does. :-)
> 
It's a reasonable approach, but not very fast or high quality.
You won't get every pixel for extreme curves, and you're calling
a lot of multiplications.
You can draw a Bezier a lot faster by forwards differencing.

First express as two cubics in x and y, with t being the time variable.

        a3 = -x0 + 3 * cpax + -3 * cpbx + x3;

	a2 = 3 * x0 + -6 * cpax + 3 * cpbx;

	a1 = -3 * x0 + 3 * cpax;

	a0 = x0

Now we can draw a cubic at 100 points by calculating 

f(t) = a0 + a1*t + a2*t^2 + a3*t^3

d  = 0.01

the forward difference algorithm becomes
t[0] = 0;
f(0) = a0;
delta1 = a1 *d + a2 *d^2 + a3*d^3
delta2 = 2*a2*d^2 + 6*a3*d^3
delta3 = 6 *a3 *d^3
for i = 1 to k do
   t[i] = t[i-1] + d
   f(t[i]) = f(t[i-1]) + delta1
  delta1 = delta1 + delta2
  delta2 = delta2 + delta3
endfor

You do that for x and y. If either delta1_x or delta1_y goes over
0.5, halve all the delta values. If it goes  below 0.125, double
them. Then you're sampling at sub-Nyquist frequency, with is 0.5
of the grid and guaranteed a pixel-perfect curve.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web