Velocity Reviews > C++ > 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?

Gavin Deane
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 11:51, "mac" <(E-Mail Removed)> 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.

Really? Because this is a C++ newsgroup. comp.lang.c is just down the
hall and will be able to help you better if C++ is not allowed.

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

There are problems with your program so far. You are seeing the nth
fibonacci number returned, but think about what memory the other
fibonacci numbers are stored in. You have explicit allocation with no
explicit deallocation, so you leak memory. The buffer you allocate
(size n*sizeof(char)) is not big enough if any of the fibonacci
numbers have more than one digit. This depends entirely on the value
of n. In C++, sizeof char is 1 by definition so multiplying n by
sizeof char is redundant. I would be surprised (but I am prepared to
be surprised) if the same is not true in C.

All of that should be fixable, but before looking for help here, can
you confirm which language you are working in? For help in C, ask in
comp.lang.c. They will be better able to help you. If you really are
happy with a C++ solution (for which the first change will be to ditch
char*, malloc and sprintf in favour of std::string) then come back
here and you will get plenty of help with that.

Gavin Deane

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:
> Hi,

Hi, this is off-topic (not C++) and obviously a coursework
so I will give you hints only

> char* Recursive(int n){
> char* a = malloc(n*sizeof(char));

(malloc returns void* not char*).

You should allocate enough space to print
all Fibonacci numbers from n to 0 with
all the commas and formatting required
so if Recursive(4) should return string like
"0,1,1,2" the allocated length should
be 8 chars not 4. It gets more complicated
for numbers with more than one digit.

!don't forget the null terminator!

> if(n == 0 || n == 1)

This will stop recursion when n==1 so 0 will
never be printed.

> sprintf(a, "%d", n);
> else
> sprintf(a, "%d", atoi(Recursive(n-1)) +
> atoi(Recursive(n-2)));

If n is not 0 you have to sprintf the
result of Recursive(n-1) which is char *
(lookup %s sprintf format specification)
and the n-th Fibonacci number and the
desired format (commas etc...).

if your initial input is 4, Recursive(4) calls
Recursive(4-1) (which returns "0,1,1")
which calls Recursive(4-2) (which returns
"0,1") etc..

Make sure you deallocate memory returned
from recursive call to Recursive (better names

> return a;
>
> }

Gavin Deane
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 12:40, "dasjotre" <(E-Mail Removed)> wrote:
> On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:
>
> > Hi,

>
> Hi, this is off-topic (not C++) and obviously a coursework
> so I will give you hints only
>
> > char* Recursive(int n){
> > char* a = malloc(n*sizeof(char));

>
> (malloc returns void* not char*).

Whether that line is correct depends on whether the OP is writing C or
C++. In C++ you need to cast the result of malloc. In C, as I
understand it, you must not cast the result of malloc. So if the code
is C, as the OP suggests, I believe it is correct.

<snip>

> > if(n == 0 || n == 1)

>
> This will stop recursion when n==1 so 0 will
> never be printed.

If n>1, the OP's Recursive function calls Recursive(n-1) AND
Recursive(n-2), so unless the recursion logic has dissolved my brain
(a possibility), n == 0 will happen when Recursive(n) for n==2 calls
Recursive(n-2).

<snip>

Gavin Deane

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 12:54, "Gavin Deane" <(E-Mail Removed)> wrote:
> On 13 Feb, 12:40, "dasjotre" <(E-Mail Removed)> wrote:
>
> > On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:

>
> > > Hi,

>
> > Hi, this is off-topic (not C++) and obviously a coursework
> > so I will give you hints only

>
> > > char* Recursive(int n){
> > > char* a = malloc(n*sizeof(char));

>
> > (malloc returns void* not char*).

>
> Whether that line is correct depends on whether the OP is writing C or
> C++. In C++ you need to cast the result of malloc. In C, as I
> understand it, you must not cast the result of malloc. So if the code
> is C, as the OP suggests, I believe it is correct.
>
> <snip>
>
> > > if(n == 0 || n == 1)

>
> > This will stop recursion when n==1 so 0 will
> > never be printed.

>
> If n>1, the OP's Recursive function calls Recursive(n-1) AND
> Recursive(n-2), so unless the recursion logic has dissolved my brain
> (a possibility), n == 0 will happen when Recursive(n) for n==2 calls
> Recursive(n-2).
>
> <snip>

Yes, but the OP's sollution is completely wrong. My hinted
sollution calls Recursive recursively only once per Recursive
(my head hurts) so n will be 0 only if Recursive is initially
called with 0.

Regards.

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 12:54, "Gavin Deane" <(E-Mail Removed)> wrote:
> On 13 Feb, 12:40, "dasjotre" <(E-Mail Removed)> wrote:
>
> > On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:

>
> > > Hi,

>
> > Hi, this is off-topic (not C++) and obviously a coursework
> > so I will give you hints only

>
> > > char* Recursive(int n){
> > > char* a = malloc(n*sizeof(char));

>
> > (malloc returns void* not char*).

>
> Whether that line is correct depends on whether the OP is writing C or
> C++. In C++ you need to cast the result of malloc. In C, as I
> understand it, you must not cast the result of malloc. So if the code
> is C, as the OP suggests, I believe it is correct.
>
> <snip>
>
> > > if(n == 0 || n == 1)

>
> > This will stop recursion when n==1 so 0 will
> > never be printed.

>
> If n>1, the OP's Recursive function calls Recursive(n-1) AND
> Recursive(n-2), so unless the recursion logic has dissolved my brain
> (a possibility), n == 0 will happen when Recursive(n) for n==2 calls
> Recursive(n-2).
>
> <snip>

Yes, but the OP's sollution is completely wrong. My hinted
sollution calls Recursive recursively only once per Recursive
(my head hurts) so n will be 0 only if Recursive is initially
called with 0.

Regards.

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 12:54, "Gavin Deane" <(E-Mail Removed)> wrote:
> On 13 Feb, 12:40, "dasjotre" <(E-Mail Removed)> wrote:
>
> > On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:

>
> > > Hi,

>
> > Hi, this is off-topic (not C++) and obviously a coursework
> > so I will give you hints only

>
> > > char* Recursive(int n){
> > > char* a = malloc(n*sizeof(char));

>
> > (malloc returns void* not char*).

>
> Whether that line is correct depends on whether the OP is writing C or
> C++. In C++ you need to cast the result of malloc. In C, as I
> understand it, you must not cast the result of malloc. So if the code
> is C, as the OP suggests, I believe it is correct.
>
> <snip>
>
> > > if(n == 0 || n == 1)

>
> > This will stop recursion when n==1 so 0 will
> > never be printed.

>
> If n>1, the OP's Recursive function calls Recursive(n-1) AND
> Recursive(n-2), so unless the recursion logic has dissolved my brain
> (a possibility), n == 0 will happen when Recursive(n) for n==2 calls
> Recursive(n-2).
>
> <snip>

Yes, but the OP's sollution is completely wrong. My hinted
sollution calls Recursive recursively only once per Recursive
(my head hurts) so n will be 0 only if Recursive is initially
called with 0.

Regards.

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 12:54, "Gavin Deane" <(E-Mail Removed)> wrote:
> On 13 Feb, 12:40, "dasjotre" <(E-Mail Removed)> wrote:
>
> > On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:

>
> > > Hi,

>
> > Hi, this is off-topic (not C++) and obviously a coursework
> > so I will give you hints only

>
> > > char* Recursive(int n){
> > > char* a = malloc(n*sizeof(char));

>
> > (malloc returns void* not char*).

>
> Whether that line is correct depends on whether the OP is writing C or
> C++. In C++ you need to cast the result of malloc. In C, as I
> understand it, you must not cast the result of malloc. So if the code
> is C, as the OP suggests, I believe it is correct.
>
> <snip>
>
> > > if(n == 0 || n == 1)

>
> > This will stop recursion when n==1 so 0 will
> > never be printed.

>
> If n>1, the OP's Recursive function calls Recursive(n-1) AND
> Recursive(n-2), so unless the recursion logic has dissolved my brain
> (a possibility), n == 0 will happen when Recursive(n) for n==2 calls
> Recursive(n-2).
>
> <snip>

Yes, but the OP's sollution is completely wrong. My hinted
sollution calls Recursive recursively only once per Recursive
(my head hurts) so n will be 0 only if Recursive is initially
called with 0.

Regards.

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 12:54, "Gavin Deane" <(E-Mail Removed)> wrote:
> On 13 Feb, 12:40, "dasjotre" <(E-Mail Removed)> wrote:
>
> > On 13 Feb, 11:51, "mac" <(E-Mail Removed)> wrote:

>
> > > Hi,

>
> > Hi, this is off-topic (not C++) and obviously a coursework
> > so I will give you hints only

>
> > > char* Recursive(int n){
> > > char* a = malloc(n*sizeof(char));

>
> > (malloc returns void* not char*).

>
> Whether that line is correct depends on whether the OP is writing C or
> C++. In C++ you need to cast the result of malloc. In C, as I
> understand it, you must not cast the result of malloc. So if the code
> is C, as the OP suggests, I believe it is correct.
>
> <snip>
>
> > > if(n == 0 || n == 1)

>
> > This will stop recursion when n==1 so 0 will
> > never be printed.

>
> If n>1, the OP's Recursive function calls Recursive(n-1) AND
> Recursive(n-2), so unless the recursion logic has dissolved my brain
> (a possibility), n == 0 will happen when Recursive(n) for n==2 calls
> Recursive(n-2).
>
> <snip>

Yes, but the OP's sollution is completely wrong. My hinted
sollution calls Recursive recursively only once per Recursive
(my head hurts) so n will be 0 only if Recursive is initially
called with 0.

Regards.

dasjotre
Guest
Posts: n/a

 02-13-2007
On 13 Feb, 13:26, "dasjotre" <(E-Mail Removed)> wrote:
<>
sorry, my reader has gone beserk.