469,950 Members | 2,362 Online

returning the fibonacci string separated by comma

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?

Feb 13 '07 #1
13 2834 On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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?
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

Feb 13 '07 #2
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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;

}

Feb 13 '07 #3
On 13 Feb, 12:40, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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

Feb 13 '07 #4
On 13 Feb, 12:54, "Gavin Deane" <deane_ga...@hotmail.comwrote:
On 13 Feb, 12:40, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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.

Feb 13 '07 #5
On 13 Feb, 12:54, "Gavin Deane" <deane_ga...@hotmail.comwrote:
On 13 Feb, 12:40, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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.

Feb 13 '07 #6
On 13 Feb, 12:54, "Gavin Deane" <deane_ga...@hotmail.comwrote:
On 13 Feb, 12:40, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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.

Feb 13 '07 #7
On 13 Feb, 12:54, "Gavin Deane" <deane_ga...@hotmail.comwrote:
On 13 Feb, 12:40, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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.

Feb 13 '07 #8
On 13 Feb, 12:54, "Gavin Deane" <deane_ga...@hotmail.comwrote:
On 13 Feb, 12:40, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 11:51, "mac" <andrei.croito...@gmail.comwrote:
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.

Feb 13 '07 #9
On 13 Feb, 13:26, "dasjotre" <dasjo...@googlemail.comwrote:
<>
sorry, my reader has gone beserk.

Feb 13 '07 #10
On 13 Feb, 13:25, "dasjotre" <dasjo...@googlemail.comwrote:
On 13 Feb, 12:54, "Gavin Deane" <deane_ga...@hotmail.comwrote:
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.
Ah - sorry, I missed that you were talking about your solution not the
OP's.

Gavin Deane

Feb 13 '07 #11
"mac" <an**************@gmail.comwrote:
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?
Has to be in C not C++? The first thing I would do is create a dynamic
string module.

// dynamic_string.h

typedef struct
{
char* begin;
char* end;
} DynamicString;

DynamicString* createString( char* with );
void releaseString( DynamicString* s );
void prependToString( DynamicString* s, char* what );
void appendToString( DynamicString* s, char* what );
void printString( DynamicString* s );

(I'll leave you to implement the above functions in the cpp file.)

Then I would use that to help solve the recursive problem.
Feb 13 '07 #12
On Feb 13, 6:51 am, "mac" <andrei.croito...@gmail.comwrote:
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?
Sounds like a homework assignment.

Feb 13 '07 #13
On 13 Feb, 17:54, "JLS" <defendu...@yahoo.comwrote:
On Feb 13, 6:51 am, "mac" <andrei.croito...@gmail.comwrote:
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.
-----------
<snip>
Sounds like a homework assignment.
So what? The OP hasn't tried to hide that fact (assuming it is a fact
- it does appear that way to me too) and has posted their code with a
description of the problem. It's not a precise description but it's as
good as many other posts here.

I don't think this group is for discussing all C++ language questions
except those that come up in the context of homework.

Gavin Deane

Feb 13 '07 #14

 3 posts views Thread by Piet | last post: by 5 posts views Thread by dnsstaiger | last post: by 1 post views Thread by idog | last post: by 5 posts views Thread by Ann Marinas | last post: by 2 posts views Thread by Roy Rodsson via .NET 247 | last post: by 14 posts views Thread by felixnielsen | last post: by 17 posts views Thread by mac | last post: by 6 posts views Thread by Andrew Tatum | last post: by 2 posts views Thread by shapper | last post: by reply views Thread by eddparker01 | last post: by reply views Thread by lanliddd | last post: by reply views Thread by isladogs | last post: by reply views Thread by Trystan | last post: by reply views Thread by Trystan | last post: by 1 post views Thread by skydivetom | last post: by reply views Thread by Romlus | last post: by reply views Thread by MikeCant | last post: by 1 post views Thread by MikeCant | last post: by