Velocity Reviews > returning the Fibonacci string separated by comma

# returning the Fibonacci string separated by comma

mac
Guest
Posts: n/a

 02-13-2007
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?

Michal Nazarewicz
Guest
Posts: n/a

 02-13-2007
"mac" <(E-Mail Removed)> 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--

Chris Dollin
Guest
Posts: n/a

 02-13-2007
Michal Nazarewicz wrote:

> "mac" <(E-Mail Removed)> 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.

mac
Guest
Posts: n/a

 02-13-2007

Chris Dollin wrote:
> Michal Nazarewicz wrote:
>
> > "mac" <(E-Mail Removed)> 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

Chris Dollin
Guest
Posts: n/a

 02-13-2007
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.

Christopher Benson-Manica
Guest
Posts: n/a

 02-13-2007
mac <(E-Mail Removed)> 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.

Chris Dollin
Guest
Posts: n/a

 02-13-2007
Christopher Benson-Manica wrote:

> mac <(E-Mail Removed)> 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.

Christopher Benson-Manica
Guest
Posts: n/a

 02-13-2007
Chris Dollin <(E-Mail Removed)> 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.

Chris Dollin
Guest
Posts: n/a

 02-13-2007
Christopher Benson-Manica wrote:

> Chris Dollin <(E-Mail Removed)> 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/.

Christopher Benson-Manica
Guest
Posts: n/a

 02-13-2007
Chris Dollin <(E-Mail Removed)> 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.