How to print an array of char backward.

[Ben Bacarisse]

To some. My point here is that it would not for me in the context of the
code.


Not really. Not in the context. >>1 reads to me the same as /2.

Well we are talking at cross-purposes then. I saw only one context
and in that context >>1 is not known to be the same as /2.

For me
that is. However I do not give bonus points to someone using >>1 for
them being "elite".


Obviously - I assumed we had that covered.

Well I am glad we agree about that (the bit you call obvious) but I
had not assumed that we had it covered. I had been assuming the OP's
code where it was, in fact, not covered.

No they are not. They are far from trivial to fix and layout and
refactoring ofetn introduce many bugs because of human error. In *my*
experience of *large* projects with *many* programmers then a consistent
layout and debugger friendly layout is a must. Fixing layout means
checking out, fixing, submitting for testing etc.

Why? I am suggesting using a tool, just prior to checking the code
into the code base. I agree that sticking to one layout is best --
don't get me wrong -- but I don't see why any more testing is called
for. Why would there be "human error"?

pro-debugger? You mean anti-debugger?

No.

That is most certainly not the case. The case supported by most regs was
based on the fact that they personally rarely used a debugger. And my
opinion of this was that most were simply posing or really had no clue
how to properly use one.

Let me get this right. You are repeating your rather diffuse
accusations of dishonesty[1]. They *say* it is personal preference,
but you don't really believe that[2]?

As one of the people whose "honesty and motivations" I thought you
were questioning before -- you never said exactly who -- I want to be
sure I have got that right.

It is impossible for a debugger to make your
life harder. It can only help. The rest is really a natural conclusion
and follow on.

I'd debate that except you seem to have made your mind up.

[1] "I seriously question the honesty and motivations of anyone here
who, as professional programmers, claim to debug such code by
reading..." in <[email protected]>.

[2] Putting aside the allowance you make for those who are honest but
clueless.

 

[Tomás Ó hÉilidhe]

No it isn't.  It is far and away the best method, assuming
sufficient stack for about 32 recursion levels.  It can be
simplified to:

void to_bin(unsigned long n) {

   if (n > 1) to_bin(n / 2);
   putchar('0' + (n % 2);

}

Isn't a function call expensive though? There's a function invocation
for each binary digit, and each function invocation will result in:
* Pushing stuff onto the stack
* Jumping to a different location
* Popping stuff off the stack
* Jumping to a different location

Surely this is gonna be way, way, WAY slower than using a loop such as
demonstrated in my most recent post in this thread, no?

Each function call will result in at least 16 bytes of stack space
also (4 bytes for int, another 4 for the char pointer, 4 for return
address, and more), and given that the function can be called
recursively 32 times, this is half a kilobyte, if not more! I'm sure
that there's plenty of microcontrollers out there that _can't_ handle
this, but there's no reason why this algorithm should be restricted to
a 3.2 GHz Intel Core Duo.

Is there anyone who has a way of testing just how big the stack gets
in this algorithm?

 

[Bartc]

Isn't a function call expensive though? There's a function invocation
for each binary digit, and each function invocation will result in:
* Pushing stuff onto the stack
* Jumping to a different location
* Popping stuff off the stack
* Jumping to a different location

Surely this is gonna be way, way, WAY slower than using a loop such as
demonstrated in my most recent post in this thread, no?

Compared with calling putchar() 32 times, these overheads are negligible.

Each function call will result in at least 16 bytes of stack space
also (4 bytes for int, another 4 for the char pointer, 4 for return
address, and more), and given that the function can be called
recursively 32 times, this is half a kilobyte, if not more!

More like 12 bytes unless the stack needs to be 8n aligned. Maybe 8 bytes if
the compiler can do without a frame pointer.

I'm sure
that there's plenty of microcontrollers out there that _can't_ handle
this, but there's no reason why this algorithm should be restricted to
a 3.2 GHz Intel Core Duo.

Is there anyone who has a way of testing just how big the stack gets
in this algorithm?

I measured it as 384 bytes on one implementation (not of C, but close
enough), to print 0x80000000.

 

[Ben Bacarisse]

Isn't a function call expensive though? There's a function invocation
for each binary digit, and each function invocation will result in:
* Pushing stuff onto the stack
* Jumping to a different location
* Popping stuff off the stack
* Jumping to a different location

Surely this is gonna be way, way, WAY slower than using a loop such as
demonstrated in my most recent post in this thread, no?

The function does IO. I expect that dominates (see below).

Each function call will result in at least 16 bytes of stack space
also (4 bytes for int, another 4 for the char pointer, 4 for return
address, and more), and given that the function can be called
recursively 32 times, this is half a kilobyte, if not more! I'm sure
that there's plenty of microcontrollers out there that _can't_ handle
this, but there's no reason why this algorithm should be restricted to
a 3.2 GHz Intel Core Duo.

Would such a limited system have putchar and unsigned longs? I ask in
genuine ignorance. A system that can't use more than 512 bytes of
stack is going to have real trouble with stdio.h (I'd have thought).

Anyway, whist the algorithm need not be limited to mainstream CPUs,
there is also no reason to limit ones programming to techniques
suitable for a very restricted microcontroller.

Is there anyone who has a way of testing just how big the stack gets
in this algorithm?

On my laptop, it uses exactly 512 bytes for a full 32 bit print. Also
some timings. I wrote a reasonable iterative version:

void to_bin_i(unsigned long n)
{
char buf[33], *p;
buf[32] = 0;
p = buf + 32;
do {
*--p = "01"[n & 1];
n >>= 1;
} while (n);
fputs(p, stdout);
}

and compared that to a version of CBFalconer's code (typo corrected):

void to_bin_r(unsigned long n)
{
if (n > 1) to_bin_r(n / 2);
putchar('0' + (n % 2));
}

To help with the IO, I timed the code when the program was writing to
/dev/null. A main that made thousands of call to each function gave
these proportions:

48.7% 0.76s to_bin_r
44.9% 0.70s to_bin_i

So, yes, the iterative version is faster, but not by a big margin.
When writing to a file, the difference is greater, because one fputs
beats a bunch of putchars:

54.1% 0.93s to_bin_r
40.7% 0.70s to_bin_i

I think you are being overly pessimistic about the cost of recursion.

[The times were done with gprof which can be unreliable when the
function is very small.]

 

[Peter Nilsson]

Good! Much better that computers learn to do what humans
are thinking, than humans learn do think like computers.

I disagree.
The code as written, is easy to understand.
If he were doing decimal representation,
he would be dividing by 10 instead.

It's entirely possible and likely that a compiler
will know as much as you do about these simple
micro-optimizations and generate the same machine
code for (x & 1) as it does for (x % 2).

That's highly unlikely on a 1c implementation. [The
code assumes dec is non-negative, but there's nothing
to tell the compiler that.]

Even on a 2c implementaiton, it's only the comparison
with zero that allows that to be true. [Note that
-1 % 2 and -1 & 1 are likely different values. They
must be different values in C99.]

 

[Richard]

Tomás Ó hÉilidhe said:


I keep seeing this claim, but I have yet to see any reasonable
justification for it as a general rule of thumb. Obviously you don't want
to call functions with a spurious frequency, but if you're going to
restructure your code to avoid them, you'd better be darn sure that it's
the function call overhead that is the problem, and that means you'd
better have profiled the code.


You blinked, and missed it. That code is way WAY faster than anything
you're actually going to notice, and you're going to have to call it a few
million times before you can even begin to notice the difference between
it and an iterative version.

This is lazy and unprofessional thinking. Using recursion here is a
total waste and would be suitable for nothing other than an exam reply
IMO.

Use what is efficient and easier on the eye - recursion is rarely so in
my experience.

If you can save time and still maintain maintainability and efficiency
then all the better. Recursion is certainly not as efficient in this
case as a loop would be. And who knows? Maybe it IS called millions of
time with stdou being piped into another CPU hungry process?

 

[Ian Collins]

This is lazy and unprofessional thinking. Using recursion here is a
total waste and would be suitable for nothing other than an exam reply
IMO.

Using recursion is the most elegant solution.

If you can save time and still maintain maintainability and efficiency
then all the better. Recursion is certainly not as efficient in this
case as a loop would be. And who knows? Maybe it IS called millions of
time with stdou being piped into another CPU hungry process?

Then you'd be calling putchar millions of times which would still
dominate the run time.

 

[vippstar]

Using recursion is the most elegant solution.


Then you'd be calling putchar millions of times which would still
dominate the run time.

Not necessarily. Truth is, comp.lang.c is not the place to talk about
efficiency in C code.
putchar is allowed to be implemented as:

int putchar(int c) { /* set error indicator in stdout */ return EOF; }
#define putchar(c) /* set error indicator in stdout */ EOF

All calls to putchar would be EOF; statements, and most, if not all
compilers would ignore a statement with no side effects.
Because of that, all calls to to_bin() are likely to be ignored
(to_bin() is a function with no return value or side effects).
The function in such situation would be... hmm O(0).

 

[Tomás Ó hÉilidhe]

Compared with calling putchar() 32 times, these overheads are negligible.

My original function fills a string, so lets make the recursive
version fill a string. For simplicity, I've made both functions print
the string with the Least Significant Bit first:

#include <stdio.h>

#define DIGITS "01"

#define BASE (sizeof DIGITS - 1)

void ConvertLoop(unsigned val, char *p)
{
do *p++ = DIGITS[val % BASE];
while (val /= BASE);

*p = 0;
}

void ConvertRecursive(unsigned const val, char *const p)
{
*p = DIGITS[val % BASE];

if (val > 1) ConvertRecursive(val / BASE,p+1);
else p[1] = 0;
}

int main(void)
{
char buf[255];

unsigned val = 65524;

ConvertLoop(val,buf);

puts(buf);

ConvertRecursive(val,buf);

puts(buf);

return 0;
}

To be honest, I've never actually seen a good recursive function that
shouldn't have been implemented as a loop. I'm not saying that there's
_never_ a case where the recursive version is better, but I've yet to
see one.

Writing recursive functions can be fun and cool for people that first
come across them, but still I'd have to go with the more efficient
code. The only real usage I have for them is doing template
metaprogramming in C++, where you can use recursion to peform
calculations at compile time:

template <unsigned x, unsigned y>
struct IntPow {
static long unsigned const value = x * IntPow<x,y-1>::value;
};

template <unsigned x>
struct IntPow<x,0> {
static long unsigned const value = 1;
};


#include <iostream>

int main(void)
{
std::cout << IntPow<3,7>::value;

int arr[ IntPow<3,3>::value ]; /* It's a compile-time constant */
}

 

[Tomás Ó hÉilidhe]

void ConvertRecursive(unsigned const val, char *const p)
{
    *p = DIGITS[val % BASE];

    if (val > 1) ConvertRecursive(val / BASE,p+1);
    else p[1] = 0;

}

Should be:

void ConvertRecursive(unsigned const val, char *p)
{
*p++ = DIGITS[val % BASE];

if (val >= BASE) ConvertRecursive(val / BASE,p);
else *p = 0;
}

 

[Chris Dollin]

To be honest, I've never actually seen a good recursive function that
shouldn't have been implemented as a loop. I'm not saying that there's
_never_ a case where the recursive version is better, but I've yet to
see one.

Parsers make a decent obvious example. Or state-machine transitions,
if they're not steered from the outside.

(One assumes, of course, that tail-call is optimised.)

 

[Bartc]

My original function fills a string, so lets make the recursive
version fill a string.

On my machine, the recursive version takes about two and half times as long.
But then the task it eventually does is fairly trivial (store a character
into an array). Still, I would also go along with the iterarive version in
this case.

Writing recursive functions can be fun and cool for people that first
come across them, but still I'd have to go with the more efficient
code.

Doing recursive stuff does my head in usually. But sometimes it is better,
and for dealing with data that is itself defined recursively (like source
code and expressions), it is just natural.

 

[Richard Tobin]

To be honest, I've never actually seen a good recursive function that
shouldn't have been implemented as a loop.

If the problem is naturally expressed recursively, why would you
convert it to a loop, unless you needed, and could achieve, a
substantial speedup? Consider expression evaluation, interpreted
programming language implementation, most kinds of parsing, game
solving, tree operations...

-- Richard

 

[Keith Thompson]

... snip ...

template <unsigned x>
struct IntPow<x,0> {
static long unsigned const value = 1;
};

#include <iostream>
int main(void) {
std::cout << IntPow<3,7>::value;

int arr[ IntPow<3,3>::value ]; /* It's a compile-time constant */
}

Your failure to learn the difference between C and C++ is fatal.

You don't really think he doesn't know the difference, do you?

He presented a chunk of C++ code as the only good example he could
think of in which recursion is useful (I disagree with him on that
point; I wouldn't seriously consider anything other than recursion to
traverse a binary tree, for example). If you want to tell him his C++
code is off-topic, go ahead and do so.

 

[Tomás Ó hÉilidhe]

He presented a chunk of C++ code as the only good example he could
think of in which recursion is useful (I disagree with him on that
point; I wouldn't seriously consider anything other than recursion to
traverse a binary tree, for example).

Firstly I'd just like to say that I'm _not_ taking the stalwart
position of "recursion is NEVER perferable over iteration", so please
don't mistake my persuasiveness for anything other than wanting to
have an enlightening, open-minded discussion.

...so with that out of the way, I'd like to ask where do you think
it's actually good to use recursion intead of iteration? Personally
I've never seen any good use for recursion other than template
metaprogramming, so it'd be great if you could give a small example.

 

[Ben Bacarisse]

My original function fills a string, so lets make the recursive
version fill a string. For simplicity, I've made both functions print
the string with the Least Significant Bit first:

IMO that is not a useful example. The recursive print is useful
precisely because it (a) get the digits the right way round (b) avoid
the need for char array.

If you need the representation in an array anyway, there is nothing to
gain from writing it using recursion.

To be honest, I've never actually seen a good recursive function that
shouldn't have been implemented as a loop. I'm not saying that there's
_never_ a case where the recursive version is better, but I've yet to
see one.

The best examples come from tree (and graph) algorithms in which I
would include parsing.

 

[Ben Bacarisse]

Firstly I'd just like to say that I'm _not_ taking the stalwart
position of "recursion is NEVER perferable over iteration", so please
don't mistake my persuasiveness for anything other than wanting to
have an enlightening, open-minded discussion.

...so with that out of the way, I'd like to ask where do you think
it's actually good to use recursion intead of iteration? Personally
I've never seen any good use for recursion other than template
metaprogramming, so it'd be great if you could give a small example.

Another has just popped back into my head: regular expression
matching. If you had to write a simple matcher in a hurry, recursion
in a natural choice. There was a long thread about this in
comp.programming recently, sparked off by this being used as an
example in the recent book "Beautiful Code". And the code is in C.

At least one of the big bookshop sites has the pertinent parts of that
chapter as a free preview.

 

[Tomás Ó hÉilidhe]

There was a long thread about this in
comp.programming recently, sparked off by this being used as an
example in the recent book "Beautiful Code".  And the code is in C.

For anyone that's interested I'm after starting a thread over on
comp.programming regarding the suitability of recursive functiosn:

http://groups.google.ie/group/comp.programming/browse_frm/thread/7ebcbeb8178bcbd4#