Velocity Reviews > Strange bug

# Strange bug

Eric Sosman
Guest
Posts: n/a

 11-22-2010
On 11/21/2010 9:40 PM, pete wrote:
> Eric Sosman wrote:
>
>> Francois' point remains, though:
>> If such problems are commonplace,
>> why do the teachers always assign exercises about Fibonacci numbers?
>> Can't they think of a problem for which recursion is useful, and not
>> just possible? I'd have thought Quicksort would make a good vehicle,
>> both for teaching the idea of recursion and for illustrating some of
>> its pitfalls -- but no, we keep seeing Fibonacci computations that
>> are described as "elegant" and take exponential running time. Pfui!

>
> I like quicksort, mergesort, and the 8 queens problem,
> as recursion exercises.

Quicksort, yes: It teaches an important algorithm, it teaches the
idea of recursion, and it shows what can go wrong with recursion. As
for the other two, I can't see why anyone would use a recursive approach
for either. (Maybe these are the same people who use recursion to fill
an N-place array with 0..N.)

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

BartC
Guest
Posts: n/a

 11-22-2010

"Eric Sosman" <(E-Mail Removed)> wrote in message
news:iccp35\$fif\$(E-Mail Removed)-september.org...
> On 11/21/2010 9:40 PM, pete wrote:
>> Eric Sosman wrote:
>>
>>> Francois' point remains, though:
>>> If such problems are commonplace,
>>> why do the teachers always assign exercises about Fibonacci numbers?
>>> Can't they think of a problem for which recursion is useful, and not
>>> just possible? I'd have thought Quicksort would make a good vehicle,
>>> both for teaching the idea of recursion and for illustrating some of
>>> its pitfalls -- but no, we keep seeing Fibonacci computations that
>>> are described as "elegant" and take exponential running time. Pfui!

>>
>> I like quicksort, mergesort, and the 8 queens problem,
>> as recursion exercises.

>
> Quicksort, yes: It teaches an important algorithm, it teaches the
> idea of recursion, and it shows what can go wrong with recursion. As

It would be teaching mostly about sorting.

> for the other two, I can't see why anyone would use a recursive approach
> for either. (Maybe these are the same people who use recursion to fill
> an N-place array with 0..N.)

I can't see the problem with examples such as Fibonacci; it is very simple;
it does show how recursion works, without other distractions; and because it
is so inefficient, it is also a good comparative benchmark *when you are
measuring the performance of function calls* (a lot of people don't get this
point).

(I had a go at implementing a fast version of the OP's Trim function; it was
about a magnitude faster, but the recursive content was so obviously
contrived, that it wasn't worth bothering with, causing a 3x slowdown over a
version using iteration. Not a good example.)

There are few other examples that might be useful: recursive or hierarchical
data structures (trees and such) are naturally handled with recursion, and
might be easier to appreciate than sorting (since the sort data is flat).
Then there is language and expression parsing. And puzzle solving. And ...

So lots of examples to draw from. Many of practical use too, although this
doesn't really matter for teaching (or benchmarking) purposes.

--
Bartc

William Hughes
Guest
Posts: n/a

 11-22-2010
On Nov 21, 11:46*pm, Eric Sosman <(E-Mail Removed)> wrote:
> On 11/21/2010 9:40 PM, pete wrote:
>
> > Eric Sosman wrote:

>
> >> Francois' point remains, though:
> >> If such problems are commonplace,
> >> why do the teachers always assign exercises about Fibonacci numbers?
> >> Can't they think of a problem for which recursion is useful, and not
> >> just possible? *I'd have thought Quicksort would make a good vehicle,
> >> both for teaching the idea of recursion and for illustrating some of
> >> its pitfalls -- but no, we keep seeing Fibonacci computations that
> >> are described as "elegant" and take exponential running time. *Pfui!

>
> > I like quicksort, mergesort, and the 8 queens problem,
> > as recursion exercises.

>
> * * *Quicksort, yes: It teaches an important algorithm, it teaches the
> idea of recursion, and it shows what can go wrong with recursion. *As
> for the other two, I can't see why anyone would use a recursive approach
> for either. *(Maybe these are the same people who use recursion to fill
> an N-place array with 0..N.)
>
> --
> Eric Sosman
> (E-Mail Removed)

As an introduction to recursion
I like Towers of Hanoi. Here is a problem that is very hard to solve
iteratively but easy to solve recursively but is simple and
does not require complex data structures. If introduction to
recursion is done using Fibonacci (or even worse factorial!)
students are likely to think, "So What?".

I prefer looking at the problem of computing finite Fourier
transforms,
to the problem of sorting.
- William Hughes

Super Ted
Guest
Posts: n/a

 11-22-2010
Well anyway, I have fixed it now with strcpy_safe. Here is the complete
working code.

#include <stdio.h>

int strcpy_safe(char *s, char *t)
{
int i = 0;
if(strlen(t) == 0)
return; // handle null strings
for(; i < strlen(t); ++i)
*(s+i) = *(t+i);
*(s+strlen(t))='\0';
return 0;
}

static int TrimWSpaceL(char *s)
{
int memmove(char *,char*);
if(isspace(*s)) {
strcpy_safe(s,s+1/*,strlen(s)*/);
return 1+TrimWSpaceL(s);
}
else
return 0;
}

static int TrimWSpaceR(char *s)
{
if(isspace(*(s+strlen(s)-1))) {
*(s+strlen(s)-1)='\0';
return 1+TrimWSpaceR(s);
}
else
return 0;
}

/* trims white-space, returning #spaces trimmed */
int TrimWSpace(char *s)
{
return TrimWSpaceL(s) + TrimWSpaceR(s);
}

int main()
{
char s[] = " \t *Hello world* \n ";
int i = TrimWSpace(s);
printf("%s\n(deleted %d spaces)\n", s,i);
return 0;
}

Ian Collins
Guest
Posts: n/a

 11-22-2010
On 11/23/10 08:43 AM, Super Ted wrote:
> Well anyway, I have fixed it now with strcpy_safe. Here is the complete
> working code.
>
> #include<stdio.h>
>
> int strcpy_safe(char *s, char *t)
> {
> int i = 0;
> if(strlen(t) == 0)
> return; // handle null strings

Empty strings, you don't test for null strings. You have also omitted
the return value.

> for(; i< strlen(t); ++i)
> *(s+i) = *(t+i);
> *(s+strlen(t))='\0';
> return 0;
> }

Why do you call strlen(t) 3 times?

> static int TrimWSpaceL(char *s)
> {
> int memmove(char *,char*);

Why don't you include <string.h>? Then you'd see this prototype is
wrong (and you don't call memmove anyway!).

--
Ian Collins

Keith Thompson
Guest
Posts: n/a

 11-22-2010
Super Ted <(E-Mail Removed)> writes:
> Well anyway, I have fixed it now with strcpy_safe. Here is the complete
> working code.
>
> #include <stdio.h>

You have calls to strlen(). You must declare it before using it,
preferably via "#include <string.h>".

You have calls to isspace(). You must declare it before using it,
preferably via "#include <ctype.h>".

> int strcpy_safe(char *s, char *t)

The identifier "strcpy_safe" is just as reserved now as it was last time
we discussed it.

> {
> int i = 0;

Making i a size_t rather than an int would make your code more portable.
Consider copying a 40000-byte string on a system with 16-bit int and
32-bit size_t.

> if(strlen(t) == 0)
> return; // handle null strings

This handles *empty* strings.

It also means that if t points to an empty string, your strcpy_safe()
does nothing. For example:

char target[] = "hello";
strcpy_safe(target, "");
printf("target = \"%s\", target);

With strcpy(), this would print
target = ""
With your strpcy_safe(), this will print:
target = "hello"

> for(; i < strlen(t); ++i)

It would be more idiomatic to write:

for (i = 0; i < strlen(t); ++i)

Or, if you can assume C99 conformance:

for (size_t i = 0; i < strlen(t); ++i)

But since you've said before that you care about efficiency, you're
calling strlen() multiple times, turning what should be an O(N)
algorithm into an O(N*M) algorithm.

Call strlen() once and save the result in a variable. Or just
detect the end of the string pointed to by t by looking for the '\0'.

> *(s+i) = *(t+i);

Do you have reason not to use array notation?

s[i] = t[i];

> *(s+strlen(t))='\0';
> return 0;
> }

You said before that you're using this strcpy_safe() because it
works with overlapping strings. Have you documented its behavior?
Have you thought about what happens with strcpy_safe(s, s+1)
vs. strcpy_safe(s+1, s)?

And even if you had gotten it right, you're likely to be paying
a substantial performance penalty for the greater flexibility.
strcpy() can be optimized in ways that depend on the assumption
that the source and target strings do not overlap.

> static int TrimWSpaceL(char *s)
> {
> int memmove(char *,char*);

Why are you declaring memmove() inside your function, why are you
declaring a function you never call, and why are you declaring
it incorrectly? You didn't even get the number of arguments right.
The only sane way to do this is to add #include <string.h> to the top
of your source file -- or, since you never call it, to leave it out.

[more code snipped]

> int main()

Do you have a reason to continue using "int main()" rather than
the more correct "int main(void)"?

[...]

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Jens Thoms Toerring
Guest
Posts: n/a

 11-22-2010
Super Ted <(E-Mail Removed)> wrote:
> Well anyway, I have fixed it now with strcpy_safe. Here is the complete
> working code.

> #include <stdio.h>

> int strcpy_safe(char *s, char *t)
> {
> int i = 0;
> if(strlen(t) == 0)
> return; // handle null strings

That's an empty string. And then a simple

if ( ! *t )
return;

is more efficient. And the 'return' call is broken since
you promised that the function would return and int but
you don't do so here.

And a final comment is: why don't you copy the
empty string to the destination when the user
is asking for it? It's a completely legal request
and most users will be rather surprised if the
function doesn;t do what (s)he askes it to do,
especially in the most simple case.

If you call your function strcpy_safe() wouldn't it
make sense to also check that neither 's' nor 't'
are NULL pointers?

> for(; i < strlen(t); ++i)
> *(s+i) = *(t+i);
> *(s+strlen(t))='\0';

Now, that's a truely inefficient implementation. You call
strlen() over and over again without any good reason.

The usual idiom for all this, whichs work perfectly well
(and much more efficient), is

while ( *s++ = *t++ )
;

> return 0;
> }

Another problem with this implementation is that you forgo
all optimizations that the normal strcpy() function can use.
A more reasonable implementation would probably be to check
if the two strings can overlap and then call either memcpy()
(if they don't) or memmove() (if the do).

And, of course, by calling the function strcpy_safe() you
have invaded the namespace that belongs to the implementa-
tion...

> static int TrimWSpaceL(char *s)
> {
> int memmove(char *,char*);

This is the name of a standard function (which is declared
in <string.h>) but which has different arguments. There
also doesn't seem to be any reason for declaring it here.
(If you want the standard memmove() function just include
<string.h> and if it's a different function give it a
different name.)

> if(isspace(*s)) {
> strcpy_safe(s,s+1/*,strlen(s)*/);
> return 1+TrimWSpaceL(s);
> }

Can you get any more inefficient? For each white-space
character you remove you do a copy and then another function
call (recursively) while simply counting how many white-
spaces there are and the do a single copy would reduce the
amount of work to be done considerably.

> else
> return 0;
> }

> static int TrimWSpaceR(char *s)
> {
> if(isspace(*(s+strlen(s)-1))) {
> *(s+strlen(s)-1)='\0';
> return 1+TrimWSpaceR(s);
> }
> else
> return 0;
> }

Similar inefficiency as with the other function.

Regards, Jens
--
\ Jens Thoms Toerring ___ (E-Mail Removed)
\__________________________ http://toerring.de

James Dow Allen
Guest
Posts: n/a

 11-22-2010
On Nov 22, 10:46*am, Eric Sosman <(E-Mail Removed)> wrote:
> * * *Quicksort, yes: It teaches an important algorithm, it teaches the
> idea of recursion, and it shows what can go wrong with recursion.

I also often choose simple looping in many problems where recursion
is plausible. Odd, that only one good example for recursion has
been presented so far - quicksort - and it's recursive only because
tail recursion can handle only one of two tails.

Let me nominate another example: digraph explorers; in particular
game tree solvers.

Even there, I'm not ashamed to confess I wrote one solver
http://fabpedigree.com/james/lesson9.htm#p93
that, to emphasize its non-recursion, does everthing in main()!

James Dow Allen

Nick
Guest
Posts: n/a

 11-22-2010
James Dow Allen <(E-Mail Removed)> writes:

> On Nov 22, 10:46Â*am, Eric Sosman <(E-Mail Removed)> wrote:
>> Â* Â* Â*Quicksort, yes: It teaches an important algorithm, it teaches the
>> idea of recursion, and it shows what can go wrong with recursion.

>
> I also often choose simple looping in many problems where recursion
> is plausible. Odd, that only one good example for recursion has
> been presented so far - quicksort - and it's recursive only because
> tail recursion can handle only one of two tails.

Working your way through naturally recursive data structures is a pretty
good one. So if you have an interpreter for a language in which you can
have arrays or lists of objects, each of which can be an array or list,
recursion is a very obviously way to, say, write the data to a file.
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk

Mark Wooding
Guest
Posts: n/a

 11-22-2010
William Hughes <(E-Mail Removed)> writes:

> As an introduction to recursion I like Towers of Hanoi. Here is a
> problem that is very hard to solve iteratively but easy to solve
> recursively but is simple and does not require complex data
> structures.

Towers of Hanoi is relatively straightforward to solve nonrecursively.
The important observation is that the binary representation of the step
number encodes the state of the game and the action to take in a fairly
simple way.

/* Determine what to do in step I of a Towers of Hanoi problem.
*
* N is the number of discs; we must have 1 <= I < 2^N. Store
* in *DD the number of the disc to move (numbered 1 up to N)
* and in *FF and *TT the numbers of the source (`from') and
* destination (`to') spindles (numbered 0, 1, 2) respectively.
* It is assumed that the overall task is to move all N discs
* from spindle 0 to spindle 2.
*/
static void hanoi_step(unsigned n, unsigned long i,
unsigned *dd, unsigned *ff, unsigned *tt)
{
unsigned m;
unsigned f = 0, t = 2, s = 1;

#define XCH(a, b) do { unsigned x = a; a = b; b = x; } while (0)

m = 1 << (n - 1);
for (; {
if (i == m) break;
else if (i & m) { XCH(f, s); i &= ~m; }
else { XCH(s, t); }
m >>= 1; n--;
}
*dd = n; *ff = f; *tt = t;

#undef XCH
}

Being able to determine a single step in the game without computing the
rest is handy if you're using a Towers of Hanoi backup schedule, for
example: you probably know how long it is since you took a full dump,
and would like to know what kind of incremental dump to do now.

> If introduction to recursion is done using Fibonacci (or
> even worse factorial!) students are likely to think, "So What?".

Recursion is an even worse way to compute Fibonacci numbers. The
following algorithm computes F(n) in time proportional to log(n)
multiplications.

/* Return the Nth Fibonacci number F(N). F(0) is defined to be
* 0 and F(1) to be 1; F(I) = F(I - 1) + F(I - 2).
*/
static unsigned long fib(unsigned n)
{
unsigned long u = 0, v = 1;
unsigned long u2, v2, iiuv, uu, vv;
unsigned m = ~0u ^ (~0u >> 1);

while (m) {
u2 = u*u; v2 = v*v; iiuv = 2*u*v;
uu = u2 + iiuv; vv = u2 + v2;
if (n & m) { u = uu + vv; v = uu; }
else { u = uu; v = vv; }
m >>= 1;
}

return (u);
}

A good algorithm to compute factorials is a little harder. If we assume
we're going to use arbitrary-precision arithmetic then multiplication is
fastest when we try to make the operands equally long, which suggests a
simple algorithm which maintains a stack with the invariant that entries
higher up in the stack are smaller. Then you push the numbers 1 up to
n, each time maintaining the invariant by popping and multiplying as
necessary. When you're done, you simply multiply the remaining entries
on the stack. Again, this is not naturally recursive.

This is probably now much faster than the algorithm used to print the
answer in decimal. A simple-minded base conversion will repeatedly take
quotient and remainder by (say) R, building up the base-R digits in
reverse order. A cleverer approach is to find the largest power R^(2^k)
smaller than the number we're meant to convert, take quotient and
remainder, and convert both separately and stitch the results together
(being careful with leading zeroes; note that R^(2^(k-1)) is an upper
bound for the power of the base needed to split the remaining parts).
This /is/ a naturally recursive algorithm, and it's very efficient; it
also has the advantage that it produces output in more or less the right
order. (There are faster ways if R is a power of 2, obviously.)

> I prefer looking at the problem of computing finite Fourier
> transforms, to the problem of sorting.

I can see the merits of that. Of course, Fourier transforms require a
certain amount of explaining in order to motivate them and explain why
the recursive algorithm is a plausible approach, but this is useful in
itself. (My university course didn't cover Fourier transforms at all.)

-- [mdw]