returning the fibonacci string separated by comma

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

  1. mac

    mac Guest

    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!
    mac, Feb 13, 2007
    #1
    1. Advertising

  2. mac

    Gavin Deane Guest

    On 13 Feb, 11:51, "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.


    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
    Gavin Deane, Feb 13, 2007
    #2
    1. Advertising

  3. mac

    dasjotre Guest

    On 13 Feb, 11:51, "mac" <> 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
    please!)

    > return a;
    >
    > }
    dasjotre, Feb 13, 2007
    #3
  4. mac

    Gavin Deane Guest

    On 13 Feb, 12:40, "dasjotre" <> wrote:
    > On 13 Feb, 11:51, "mac" <> 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
    Gavin Deane, Feb 13, 2007
    #4
  5. mac

    dasjotre Guest

    On 13 Feb, 12:54, "Gavin Deane" <> wrote:
    > On 13 Feb, 12:40, "dasjotre" <> wrote:
    >
    > > On 13 Feb, 11:51, "mac" <> 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, Feb 13, 2007
    #5
  6. mac

    dasjotre Guest

    On 13 Feb, 12:54, "Gavin Deane" <> wrote:
    > On 13 Feb, 12:40, "dasjotre" <> wrote:
    >
    > > On 13 Feb, 11:51, "mac" <> 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, Feb 13, 2007
    #6
  7. mac

    dasjotre Guest

    On 13 Feb, 12:54, "Gavin Deane" <> wrote:
    > On 13 Feb, 12:40, "dasjotre" <> wrote:
    >
    > > On 13 Feb, 11:51, "mac" <> 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, Feb 13, 2007
    #7
  8. mac

    dasjotre Guest

    On 13 Feb, 12:54, "Gavin Deane" <> wrote:
    > On 13 Feb, 12:40, "dasjotre" <> wrote:
    >
    > > On 13 Feb, 11:51, "mac" <> 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, Feb 13, 2007
    #8
  9. mac

    dasjotre Guest

    On 13 Feb, 12:54, "Gavin Deane" <> wrote:
    > On 13 Feb, 12:40, "dasjotre" <> wrote:
    >
    > > On 13 Feb, 11:51, "mac" <> 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, Feb 13, 2007
    #9
  10. mac

    dasjotre Guest

    On 13 Feb, 13:26, "dasjotre" <> wrote:
    <>
    sorry, my reader has gone beserk.
    dasjotre, Feb 13, 2007
    #10
  11. mac

    Gavin Deane Guest

    On 13 Feb, 13:25, "dasjotre" <> wrote:
    > On 13 Feb, 12:54, "Gavin Deane" <> wrote:
    > > 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.

    My head hurts too.

    Gavin Deane
    Gavin Deane, Feb 13, 2007
    #11
  12. mac

    Daniel T. Guest

    In article <>,
    "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?


    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.
    Daniel T., Feb 13, 2007
    #12
  13. mac

    JLS Guest

    On Feb 13, 6:51 am, "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!


    Sounds like a homework assignment.
    JLS, Feb 13, 2007
    #13
  14. mac

    Gavin Deane Guest

    On 13 Feb, 17:54, "JLS" <> wrote:
    > On Feb 13, 6:51 am, "mac" <> wrote:
    > > 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
    Gavin Deane, Feb 13, 2007
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Rilling

    Array to a comma Separated String

    Peter Rilling, Jul 8, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    504
  2. =?Utf-8?B?Q2hyaXMgTGFuZQ==?=

    How to stream a comma separated string to the browser?

    =?Utf-8?B?Q2hyaXMgTGFuZQ==?=, Jul 21, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    349
    =?Utf-8?B?Q2hyaXMgTGFuZQ==?=
    Jul 21, 2006
  3. ronan_40060

    Parsing a Comma Separated String in C

    ronan_40060, Sep 6, 2006, in forum: C Programming
    Replies:
    1
    Views:
    2,259
    Rudresh R kaddipudi
    Dec 22, 2006
  4. mac
    Replies:
    17
    Views:
    601
    CBFalconer
    Feb 14, 2007
  5. NickPick
    Replies:
    7
    Views:
    548
    Arne Vajhøj
    Mar 3, 2009
Loading...

Share This Page