returning the Fibonacci string separated by comma

[mac]

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!

 

[Michal Nazarewicz]

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-

 

[Chris Dollin]

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

 

[mac]

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

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

 

[Chris Dollin]

Chris Dollin wrote:

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.

 

[Christopher Benson-Manica]

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.

 

[Chris Dollin]

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.

 

[Christopher Benson-Manica]

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.

 

[Chris Dollin]

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

 

[Christopher Benson-Manica]

Christopher Benson-Manica wrote:

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.

 

[Ben Bacarisse]

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)
to fib(1)). My code is sufficiently bad (no comments and rather
dubious style in places) that despite this being homework I might
post it if you post another significant attempt.

 

[gw7rib]

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

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
add them up.

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.

 

[Christopher Benson-Manica]

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

 

[Chris Dollin]

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.

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.

 

[Christopher Benson-Manica]

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

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.

 

[Chris Dollin]

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?

 

[Christopher Benson-Manica]

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

 

[CBFalconer]

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.

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