returning the Fibonacci string separated by comma

Discussion in 'C Programming' started by mac, Feb 13, 2007.

1. macGuest

Hi,

I'm trying to write a fibonacci recursive function that will return
the fibonacci string separated by comma. The problem sounds like this:
-------------
Write a recursive function that creates a character string containing
the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
F(1) = 1 -, separated by comma. n should be given as an argument to
the program. The recursive function should only take one parameter, n,
and should return the string. You will not use any extra function.

Do not try to optimize for space or speed. Do not assume any maximum
length for the result string. Also, please don't use global / static
variables.
-----------

The code must be in C. I managed to create a function that returns the
fibonacci value for the specified 'N' as a char*, but I didn't manage
to get the entire string separated by comma.
This is my function:

char* Recursive(int n){
char* a = malloc(n*sizeof(char));
if(n == 0 || n == 1)
sprintf(a, "%d", n);
else
sprintf(a, "%d", atoi(Recursive(n-1)) +
atoi(Recursive(n-2)));
return a;
}

How could I get the entire string?

mac, Feb 13, 2007

2. Michal NazarewiczGuest

"mac" <> writes:
> I'm trying to write a fibonacci recursive function that will return
> the fibonacci string separated by comma. The problem sounds like this:
> -------------
> Write a recursive function that creates a character string containing
> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
> F(1) = 1 -, separated by comma. n should be given as an argument to
> the program. The recursive function should only take one parameter, n,
> and should return the string. You will not use any extra function.
>
> Do not try to optimize for space or speed. Do not assume any maximum
> length for the result string. Also, please don't use global / static
> variables.
> -----------
>
> The code must be in C. I managed to create a function that returns the
> fibonacci value for the specified 'N' as a char*, but I didn't manage
> to get the entire string separated by comma.
> This is my function:
>
> char* Recursive(int n){
> char* a = malloc(n*sizeof(char));
> if(n == 0 || n == 1)
> sprintf(a, "%d", n);
> else
> sprintf(a, "%d", atoi(Recursive(n-1)) +
> atoi(Recursive(n-2)));
> return a;
> }

atoi is useless here. What you are doing is first convert integer into
a string and then back into an integer - waste of time. Moreover, you
never free memory you allocate. You should first calculate the value
and then convert it into string:

#v+
long fib(int n) {
return n<2 ? 1 : fib(n-1) + fib(n-2);
}

char *fibstr(int n) {
char *str = malloc(10); /* 10 should be enough */
/* FIXME: error checking ommited */
sprintf(str, "%ld", fib(n);
return str;
}
#v-

Then you can use something like:

#v+
for (i = 0; i<=n; ++i) {
char *str = fibstr(i);
/* FIXME: need to check buffor size and realloc() if needed */
sprintf(buf, "%s%s,", buf, str);
free(str);
}
buf[strlen(buf)] = 0;
#v-

or even better:

#v+
/* FIXME: buffer overflow checking */
char *fibstr(char *dest, int n) {
sprintF(dest, "%ld", fib(n));
return dest;
}

char *foo(int n) {
char str[10];
/* ... */

for (i = 0; i<=n; ++i) {
/* FIXME: need to check buffor size and realloc() if needed */
sprintf(buf, "%s%s,", buf, fibstr(str, i));
}
buf[strlen(buf)] = 0;

/* ... */
}
#v-

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--

Michal Nazarewicz, Feb 13, 2007

3. Chris DollinGuest

Michal Nazarewicz wrote:

> "mac" <> writes:
>> I'm trying to write a fibonacci recursive function that will return
>> the fibonacci string separated by comma. The problem sounds like this:
>> -------------
>> Write a recursive function that creates a character string containing
>> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
>> F(1) = 1 -, separated by comma. n should be given as an argument to
>> the program. The recursive function should only take one parameter, n,
>> and should return the string. You will not use any extra function.
>>
>> Do not try to optimize for space or speed. Do not assume any maximum
>> length for the result string. Also, please don't use global / static
>> variables.
>> -----------
>>
>> The code must be in C. I managed to create a function that returns the
>> fibonacci value for the specified 'N' as a char*, but I didn't manage
>> to get the entire string separated by comma.
>> This is my function:
>>
>> char* Recursive(int n){
>> char* a = malloc(n*sizeof(char));
>> if(n == 0 || n == 1)
>> sprintf(a, "%d", n);
>> else
>> sprintf(a, "%d", atoi(Recursive(n-1)) +
>> atoi(Recursive(n-2)));
>> return a;
>> }

>
> atoi is useless here.
> What you are doing is first convert integer into
> a string and then back into an integer - waste of time.

"Do not try to optimize for space or speed."

> Moreover, you
> never free memory you allocate.

"Do not try to optimize for space or speed."

> You should first calculate the value
> and then convert it into string:
>
> #v+
> long fib(int n) {
> return n<2 ? 1 : fib(n-1) + fib(n-2);
> }

"You will not use any extra function."

> char *fibstr(int n) {
> char *str = malloc(10); /* 10 should be enough */
> /* FIXME: error checking ommited */
> sprintf(str, "%ld", fib(n);
> return str;
> }
> #v-
> Then you can use something like:
>
> #v+
> for (i = 0; i<=n; ++i) {
> char *str = fibstr(i);
> /* FIXME: need to check buffor size and realloc() if needed */
> sprintf(buf, "%s%s,", buf, str);
> free(str);
> }
> buf[strlen(buf)] = 0;

What?

> #v-
>
> or even better:
>
> #v+
> /* FIXME: buffer overflow checking */
> char *fibstr(char *dest, int n) {
> sprintF(dest, "%ld", fib(n));
> return dest;
> }
>
> char *foo(int n) {
> char str[10];
> /* ... */
>
> for (i = 0; i<=n; ++i) {
> /* FIXME: need to check buffor size and realloc() if needed */
> sprintf(buf, "%s%s,", buf, fibstr(str, i));
> }
> buf[strlen(buf)] = 0;
>
> /* ... */
> }
> #v-

Well, you're going all around the houses for what's a relatively
straightforward problem, and ignoring the solution conditions
to boot. (I'm assuming the "extra functions" you're not allowed
to use aren't C library functions -- otherwise the problem is
insoluble ...)

--
Chris "electric hedgehog" Dollin
The shortcuts are all full of people using them.

Chris Dollin, Feb 13, 2007
4. macGuest

Chris Dollin wrote:
> Michal Nazarewicz wrote:
>
> > "mac" <> writes:
> >> I'm trying to write a fibonacci recursive function that will return
> >> the fibonacci string separated by comma. The problem sounds like this:
> >> -------------
> >> Write a recursive function that creates a character string containing
> >> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
> >> F(1) = 1 -, separated by comma. n should be given as an argument to
> >> the program. The recursive function should only take one parameter, n,
> >> and should return the string. You will not use any extra function.
> >>
> >> Do not try to optimize for space or speed. Do not assume any maximum
> >> length for the result string. Also, please don't use global / static
> >> variables.
> >> -----------
> >>
> >> The code must be in C. I managed to create a function that returns the
> >> fibonacci value for the specified 'N' as a char*, but I didn't manage
> >> to get the entire string separated by comma.
> >> This is my function:
> >>
> >> char* Recursive(int n){
> >> char* a = malloc(n*sizeof(char));
> >> if(n == 0 || n == 1)
> >> sprintf(a, "%d", n);
> >> else
> >> sprintf(a, "%d", atoi(Recursive(n-1)) +
> >> atoi(Recursive(n-2)));
> >> return a;
> >> }

> >
> > atoi is useless here.
> > What you are doing is first convert integer into
> > a string and then back into an integer - waste of time.

>
> "Do not try to optimize for space or speed."
>
> > Moreover, you
> > never free memory you allocate.

>
> "Do not try to optimize for space or speed."
>
> > You should first calculate the value
> > and then convert it into string:
> >
> > #v+
> > long fib(int n) {
> > return n<2 ? 1 : fib(n-1) + fib(n-2);
> > }

>
> "You will not use any extra function."
>
> > char *fibstr(int n) {
> > char *str = malloc(10); /* 10 should be enough */
> > /* FIXME: error checking ommited */
> > sprintf(str, "%ld", fib(n);
> > return str;
> > }
> > #v-
> > Then you can use something like:
> >
> > #v+
> > for (i = 0; i<=n; ++i) {
> > char *str = fibstr(i);
> > /* FIXME: need to check buffor size and realloc() if needed */
> > sprintf(buf, "%s%s,", buf, str);
> > free(str);
> > }
> > buf[strlen(buf)] = 0;

>
> What?
>
> > #v-
> >
> > or even better:
> >
> > #v+
> > /* FIXME: buffer overflow checking */
> > char *fibstr(char *dest, int n) {
> > sprintF(dest, "%ld", fib(n));
> > return dest;
> > }
> >
> > char *foo(int n) {
> > char str[10];
> > /* ... */
> >
> > for (i = 0; i<=n; ++i) {
> > /* FIXME: need to check buffor size and realloc() if needed */
> > sprintf(buf, "%s%s,", buf, fibstr(str, i));
> > }
> > buf[strlen(buf)] = 0;
> >
> > /* ... */
> > }
> > #v-

>
> Well, you're going all around the houses for what's a relatively
> straightforward problem, and ignoring the solution conditions
> to boot. (I'm assuming the "extra functions" you're not allowed
> to use aren't C library functions -- otherwise the problem is
> insoluble ...)
>
> --
> Chris "electric hedgehog" Dollin
> The shortcuts are all full of people using them.

The C library functions are allowed ... I'm using strcat, atoi,
itoa .... but still didn't manage to get it right ... I fell I'm close
to the solutions ... but yet doesn't work

mac, Feb 13, 2007
5. Chris DollinGuest

mac wrote:

>
> Chris Dollin wrote:

>> (I'm assuming the "extra functions" you're not allowed
>> to use aren't C library functions -- otherwise the problem is
>> insoluble ...)

> The C library functions are allowed ... I'm using strcat, atoi,
> itoa ....

`itoa` isn't a Standard C function. I used `sprintf` for the
job. (And `strtol` rather than `atoi`, because used `long` as
the type for the fibonacci results.)

> but still didn't manage to get it right ... I fell I'm close
> to the solutions ... but yet doesn't work

Three clues. One: it's not difficult. If your code for this is
complicated, something is wrong. Two: strings are the poor
man's lists. Three: write tests [1]. (You can throw them away
before you submit so they don't count as "extra functions".)

By the way, the result string can have the numbers in either
order - largest first or smallest first. I've done largest
first, but switching order around is trivial. Does it matter?

[1] OK, OK, so I didn't. My only excuse is that the code worked
first time [2].

[2] Not counting missing out a printf argument in the output
function, and forgetting to compile with enough options.
Fortunately, `fibs(134514416) = Â¨Â¨Â®Â¿Ã¤4` was a bit of a
giveaway.

--
Chris "electric hedgehog" Dollin
Meaning precedes definition.

Chris Dollin, Feb 13, 2007
6. Christopher Benson-ManicaGuest

mac <> wrote:

> char* Recursive(int n){
> char* a = malloc(n*sizeof(char));
> if(n == 0 || n == 1)
> sprintf(a, "%d", n);
> else
> sprintf(a, "%d", atoi(Recursive(n-1)) +
> atoi(Recursive(n-2)));
> return a;
> }

> How could I get the entire string?
> Thanks in advance for help!

You're on the right track. First, think about storing Recursive(n-1)
and Recursive(n-2) in separate char * variables - you'll need to free
the memory they point to (at the right time), and you need them both
to determine the string for (n-1) and to compute the current Fibonacci
number (as you've done with atoi). Think about what you *really* want
to return for n == 1 and n == 0. Also think about that call to
malloc; you aren't malloc'ing enough memory, first of all.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

Christopher Benson-Manica, Feb 13, 2007
7. Chris DollinGuest

Christopher Benson-Manica wrote:

> mac <> wrote:
>
>> char* Recursive(int n){
>> char* a = malloc(n*sizeof(char));
>> if(n == 0 || n == 1)
>> sprintf(a, "%d", n);
>> else
>> sprintf(a, "%d", atoi(Recursive(n-1)) +
>> atoi(Recursive(n-2)));
>> return a;
>> }

>
>> How could I get the entire string?
>> Thanks in advance for help!

>
> You're on the right track. First, think about storing Recursive(n-1)
> and Recursive(n-2) in separate char * variables - you'll need to free
> the memory they point to (at the right time),

He doesn't. That would be an optimisation for space.

--
Chris "electric hedgehog" Dollin
A rock is not a fact. A rock is a rock.

Chris Dollin, Feb 13, 2007
8. Christopher Benson-ManicaGuest

Chris Dollin <> wrote:

> > You're on the right track. First, think about storing Recursive(n-1)
> > and Recursive(n-2) in separate char * variables - you'll need to free
> > the memory they point to (at the right time),

> He doesn't. That would be an optimisation for space.

I wouldn't personally call avoiding memory leaks an "optimization for
space", and I wouldn't call a class assigning a homework assignment
permitting memory leaks in the solution worthwhile. OP's MMV.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

Christopher Benson-Manica, Feb 13, 2007
9. Chris DollinGuest

Christopher Benson-Manica wrote:

> Chris Dollin <> wrote:
>
>> > You're on the right track. First, think about storing Recursive(n-1)
>> > and Recursive(n-2) in separate char * variables - you'll need to free
>> > the memory they point to (at the right time),

>
>> He doesn't. That would be an optimisation for space.

>
> I wouldn't personally call avoiding memory leaks an "optimization for
> space",

What else is it?

> and I wouldn't call a class assigning a homework assignment
> permitting memory leaks in the solution worthwhile. OP's MMV.

It's not the OP's M; it's their instructor's M. One can reasonably
assume that the point of the exercise is to learn something about
recursion and/or Strings For Things; worrying about a space leak
is a distraction [1]. Maybe the optimisation aspects are the /next/
lesson.

It's because we're specifically told that we're not optimising for
time that I haven't mentioned the exponential pessimisation that
the code I wrote doesn't have.

[1] I do wonder if the OPs environment has really thought about
the language they use for teaching. But in this case I think
it falls under "don't second-guess the guys at the sharp end".

--
Chris "electric hedgehog" Dollin
Scoring, bah. If I want scoring I'll go play /Age of Steam/.

Chris Dollin, Feb 13, 2007
10. Christopher Benson-ManicaGuest

Chris Dollin <> wrote:

> Christopher Benson-Manica wrote:

> > I wouldn't personally call avoiding memory leaks an "optimization for
> > space",

> What else is it?

Optimizing for correctness?

> It's because we're specifically told that we're not optimising for
> time that I haven't mentioned the exponential pessimisation that
> the code I wrote doesn't have.

IMO code can be time-inefficient and still be correct. I don't
consider code that leaks memory to be correct.

> [1] I do wonder if the OPs environment has really thought about
> the language they use for teaching. But in this case I think
> it falls under "don't second-guess the guys at the sharp end".

If the goal is to learn about recursion, the problem is a poor one. I
really don't think there's a good rationale for allowing memory leaks;
if the class is geared toward non-technology majors, it should be
tought in a different language, and if it is geared toward technology
majors it is mis-educating them.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

Christopher Benson-Manica, Feb 13, 2007
11. Ben BacarisseGuest

"mac" <> writes:

> Hi,
>
> I'm trying to write a fibonacci recursive function that will return
> the fibonacci string separated by comma. The problem sounds like this:
> -------------
> Write a recursive function that creates a character string containing
> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
> F(1) = 1 -, separated by comma. n should be given as an argument to
> the program. The recursive function should only take one parameter, n,
> and should return the string. You will not use any extra function.

I am not a fan of this sort of restriction. For one, it forces you
into a particular design, and for another using extra functions is
almost always A Good Thing.

> Do not try to optimize for space or speed. Do not assume any maximum
> length for the result string. Also, please don't use global / static
> variables.

If you are not to assume a maximum length, you should not really be
using integer arithmetic. This is a guess. The problem is rather
"coded" but if you are to use integer arithmetic (even long long) then
the strings will be so short that assuming their length would the
obvious thing to do.

You know the prototype will be:

char *fib(int n)

Write down what fib(0), fib(1)... fib(5) look like. Think what you
need to do to fib(n-1) to get fib(n). Can you do it without integer
arithmetic?

I did it producing the list from fib(1) up to fib(n). It is, I think,
slightly simpler if you make the list appear from big to small (fib(n)
dubious style in places) that despite this being homework I might
post it if you post another significant attempt.

--
Ben.

Ben Bacarisse, Feb 13, 2007
12. Guest

On 13 Feb, 11:50, "mac" <> wrote:
> Hi,
>
> I'm trying to write a fibonacci recursive function that will return
> the fibonacci string separated by comma. The problem sounds like this:
> -------------
> Write a recursive function that creates a character string containing
> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
> F(1) = 1 -, separated by comma. n should be given as an argument to
> the program. The recursive function should only take one parameter, n,
> and should return the string. You will not use any extra function.
>
> Do not try to optimize for space or speed. Do not assume any maximum
> length for the result string. Also, please don't use global / static
> variables.
> -----------
>
> The code must be in C. I managed to create a function that returns the
> fibonacci value for the specified 'N' as a char*, but I didn't manage
> to get the entire string separated by comma.
> This is my function:
>
> char* Recursive(int n){
> char* a = malloc(n*sizeof(char));
> if(n == 0 || n == 1)
> sprintf(a, "%d", n);
> else
> sprintf(a, "%d", atoi(Recursive(n-1)) +
> atoi(Recursive(n-2)));
> return a;
>
> }
>
> How could I get the entire string?
> Thanks in advance for help!

You haven't said exactly what is troubling you, but it looks as though
you are having difficulties allocating the space for the string. The
problem says you must not assume a maximum string length, so it looks
as though you are going to have to keep malloc'ing longer and longer
spaces until you are finished. This is a bit of an inefficient way of
going about things, but you have been told you don't need to worry

So I think you need something along the lines of:

char* Recursive(int n){
char *a, *b;

if(n == 0 || n == 1) deal with end of recursion
a = Recursive(n-1);
b = malloc(strlen(a) plus a bit more);
load up b with the contents of a and the new value
free(a);
return b;
}

This still leaves you to work out how to calculate the new value, of
course - if you're having trouble with this, make sure you are getting
the right values, make sure there will always be two of them, and then

I'd be inclined to include the "free" line, though as Chris says, this
might be considered an optimisation for space that you aren't allowed
to do.

Hope this helps.
Paul.

, Feb 13, 2007
13. Christopher Benson-ManicaGuest

wrote:

> char* Recursive(int n){
> char *a, *b;

> if(n == 0 || n == 1) deal with end of recursion
> a = Recursive(n-1);
> b = malloc(strlen(a) plus a bit more);
> load up b with the contents of a and the new value

Sounds like a job for "char *c=Recursive(n-2)".

> free(a);

And free(c).

> I'd be inclined to include the "free" line, though as Chris says, this
> might be considered an optimisation for space that you aren't allowed
> to do.

I certainly didn't read the specs as prohibiting optimizations, and as
I've said elsethread, I disagree with the idea that avoiding memory
leaks is an "optimization for space".

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

Christopher Benson-Manica, Feb 13, 2007
14. Chris DollinGuest

Christopher Benson-Manica wrote:

> Chris Dollin <> wrote:
>
>> Christopher Benson-Manica wrote:

>
>> > I wouldn't personally call avoiding memory leaks an "optimization for
>> > space",

>
>> What else is it?

>
> Optimizing for correctness?

No, it's certainly not /that/.

You can leave the `free`s out and the code will produce the correct
answer string (if malloc doesn't fail, which you have no control
over anyway). The only reason to put the `free`s in is to reduce
the space use. That's an optimisation for space.

Now, I agree that it's a /very important/ optimisation for space,
and that if the OP's instructor doesn't deal with the issue RSN
that they're doing them [1] a disservice. But one can't teach
everything at once.

>> It's because we're specifically told that we're not optimising for
>> time that I haven't mentioned the exponential pessimisation that
>> the code I wrote doesn't have.

>
> IMO code can be time-inefficient and still be correct. I don't
> consider code that leaks memory to be correct.

I don't see why you can think of space-wasting as "incorrectness"
and time-wasting as not. If the code takes more than the decreed
time it's just as incorrect than if it takes more than the decreed
space.

My space-wasting implementation of the OP's problem does fib(50)
in the blink of an eye (and uses only a "little" space per
outermost call). My space-efficient just-calculate-fib-n
implementation takes -- oh, it's still running. Hang on a bit.

>> [1] I do wonder if the OPs environment has really thought about
>> the language they use for teaching. But in this case I think
>> it falls under "don't second-guess the guys at the sharp end".

>
> If the goal is to learn about recursion, the problem is a poor one.

Why do you think so? I think the example is pleasingly rich, a lot
richer than the usual `calculate fib(n) by recursion` stuff we see.
The string-hacking makes a difference that I /hope/ the instructor
intends to exploit.

> I
> really don't think there's a good rationale for allowing memory leaks;
> if the class is geared toward non-technology majors, it should be
> tought in a different language,

I concur.

> and if it is geared toward technology
> majors it is mis-educating them.

I think (perhaps over-optimistically) that the /explicit/ "don't optimise"
in the specification means that the optimisation considerations will come
later. We don't know enough about the instructor and their course to judge
whether or not it's mis-educating the OP and their co-students.

[Six minutes. I'm not going to try it on 80.]

[1] Want. Lojban. Pronouns.

--
Chris "electric hedgehog" Dollin
A rock is not a fact. A rock is a rock.

Chris Dollin, Feb 14, 2007
15. Christopher Benson-ManicaGuest

Chris Dollin <> wrote:

> You can leave the `free`s out and the code will produce the correct
> answer string (if malloc doesn't fail, which you have no control
> over anyway). The only reason to put the `free`s in is to reduce
> the space use. That's an optimisation for space.

> Now, I agree that it's a /very important/ optimisation for space,
> ...

I don't have any good rejoinder to that, so I suppose I'll concede the
point.

> I don't see why you can think of space-wasting as "incorrectness"
> and time-wasting as not.

Again conceded - I don't believe anyone would characterize bogosort as
"correct".

> > If the goal is to learn about recursion, the problem is a poor one.

> Why do you think so?

Mainly because it seems to have unnecessarily introduced a new concept
- memory allocation - which the problem statement suggests the student
does not yet understand fully.

> I think (perhaps over-optimistically) that the /explicit/ "don't optimise"
> in the specification means that the optimisation considerations will come
> later.

I would certainly hope so, but even so I would prefer a more logical
progression of course topics.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

Christopher Benson-Manica, Feb 14, 2007
16. Chris DollinGuest

Christopher Benson-Manica wrote:

> Chris Dollin <> wrote:

>> I think (perhaps over-optimistically) that the /explicit/ "don't optimise"
>> in the specification means that the optimisation considerations will come
>> later.

>
> I would certainly hope so, but even so I would prefer a more logical
> progression of course topics.

I would put optimisation after doing-something[-useful]. Preferably not
/long/ after ...

I wonder if the OP has got anywhere yet?

--
Chris "electric hedgehog" Dollin
"Reaching out for mirrors hidden in the web." - Renaissance, /Running Hard/

Chris Dollin, Feb 14, 2007
17. Christopher Benson-ManicaGuest

Chris Dollin <> wrote:

> I would put optimisation after doing-something[-useful]. Preferably not
> /long/ after ...

I still hesitate to call it "optimization" when failing to do it on a
test will (hopefully) result in points off, and failing to do it on a
job interview will (hopefully) result in the applicant not being
hired. I personally prefer do-everything-right ->
do-something[-useful], but mileage clearly varies here.

> I wonder if the OP has got anywhere yet?

Probably long gone, as usual...

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

Christopher Benson-Manica, Feb 14, 2007
18. CBFalconerGuest

Chris Dollin wrote:
> Christopher Benson-Manica wrote:
>> Chris Dollin <> wrote:
>>> Christopher Benson-Manica wrote:

>>
>>>> I wouldn't personally call avoiding memory leaks an "optimization
>>>> for space",

>>
>>> What else is it?

>>
>> Optimizing for correctness?

>
> No, it's certainly not /that/.
>
> You can leave the `free`s out and the code will produce the correct
> answer string (if malloc doesn't fail, which you have no control
> over anyway). The only reason to put the `free`s in is to reduce
> the space use. That's an optimisation for space.
>
> Now, I agree that it's a /very important/ optimisation for space,
> and that if the OP's instructor doesn't deal with the issue RSN
> that they're doing them [1] a disservice. But one can't teach
> everything at once.
>
>>> It's because we're specifically told that we're not optimising
>>> for time that I haven't mentioned the exponential pessimisation
>>> that the code I wrote doesn't have.

>>
>> IMO code can be time-inefficient and still be correct. I don't
>> consider code that leaks memory to be correct.

>
> I don't see why you can think of space-wasting as "incorrectness"
> and time-wasting as not. If the code takes more than the decreed
> time it's just as incorrect than if it takes more than the decreed
> space.
>
> My space-wasting implementation of the OP's problem does fib(50)
> in the blink of an eye (and uses only a "little" space per
> outermost call). My space-efficient just-calculate-fib-n
> implementation takes -- oh, it's still running. Hang on a bit.

Is the following a space wasting implementation?

/* returns ULONG_MAX for overflow */
unsigned long fibo(unsigned int n)
{
unsigned long pprev, prev, value;

if ((pprev = 0) == n) value = pprev;
else if ((prev = 1) == n) value = prev;
else do {
value = pprev + prev; pprev = prev; prev = value;
if (value < pprev) {
value = -1; /* ULONG_MAX, overflow */
goto x;
}
} while (2 <= --n);
x: return value;
} /* fibo */

(overflows at 48 for minimum size unsigned long)

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

CBFalconer, Feb 14, 2007