Visual recursion

Discussion in 'C Programming' started by rrice899, Jul 9, 2013.

  1. rrice899

    rrice899 Guest

    Hi,
    I want to look at how recursion works. So I modified another recursion file with some code to print a dash ('-') starting from an empty char pointer "*s". Then concatenating the dash to 's'. But I can't get it to print or even run. There is one error:
    line 11 error: expected ')' before string constant.
    This is my first post and I'm just learning c(teaching myself). I apologize for any transgressions. I appreciate any comments. Below is the program:

    #include <stdio.h>
    #include <string.h>
    void towers(int, char, char, char);
    void towers(int n, char frompeg, char topeg, char auxpeg){
    int indent = 10;
    int i;
    char *str = "";
    {
    for(i = 0; i < indent; i++)
    {
    char *strcat(str, "-");
    }
    if(n > 0){
    towers(n-1, frompeg, auxpeg, topeg);
    printf("\nMove disk %d from peg %c to peg %c\n", n, frompeg, topeg);
    indent = indent +1;
    printf("%c\n", *str);
    towers(n-1, auxpeg, topeg, frompeg);
    indent = indent + 1;
    }
    }
    }
    int main(){
    int n = 2;
    printf("The tower of Hanoi involves the moves: \n\n");
    towers(n, 'A', 'C', 'B');
    return 0;
    }
     
    rrice899, Jul 9, 2013
    #1
    1. Advertisements

  2. rrice899

    James Kuyper Guest

    This code causes the creation of an array of char of length 1,
    containing '\0'. It also sets str to point at the first (and only)
    element of that array. Your program has undefined behavior if it makes
    any attempt to write to that array.
    This is the line that the compiler was complaining about. It's just
    plain wrong, but it's so wrong that I'm having a hard time deciding how
    to to describe what's wrong with it. Your compiler had trouble too - the
    error message it produced doesn't make things any clearer.

    The 'char *' portion only makes sense if you are writing a declaration.
    You don't need to declare strcat(), because it is declared in
    <string.h>. You've already #included <string.h>, so you shouldn't
    re-declare it.
    On the other hand, the (str, "-") part looks like you're trying to call
    strcat(), rather than declare it.

    It's possible to declare something on the same line that calls a
    function, but that isn't the way to do so. My best guess is that you
    intended to write something like this:

    char *q = strcat(str, "-");

    However, there's no need to save the value returned by a function in a
    variable, unless you intend to do something with that value. It's
    perfectly acceptable to write

    strcat(str, "-");

    except for the following issue: the first time it's called, strcat()
    will attempt to write '-' in the place pointed at by str. Such a write
    has undefined behavior, because str points at the array allocated to
    store a string literal. Even if that array were writable, you'd still
    have problems, because the second thing that strcat() will try to do is
    write a '\0' in the position one past the end of that array, which also
    has undefined behavior.

    What you need to do in cases like this is to allocate an actual buffer
    that is guaranteed to be long enough (and determining how long it needs
    to be can be a problem in cases like this):

    #define LONG_ENOUGH 256
    char str[LONG_ENOUGH] = "";

    This line creates a writable array named str, of length LONG_ENOUGH, and
    initialized it with all zeros. The first zero is copied from the string
    literal. Because one element of the array was initialized explicitly,
    all of the other elements of the array are initialized to the default
    value, which happens to be zero, too.
     
    James Kuyper, Jul 9, 2013
    #2
    1. Advertisements

  3. rrice899

    James Kuyper Guest

    Almost certainly - but the usual rule (you're free to follow a different
    one), is that we won't do homework for people, but that we will help
    them if they make a serious attempt to do it themselves. This one looks
    fairly serious to me.

    ....
    The function towers() is defined on lines 4-22. That definition includes
    two calls to towers(), on lines 14 and 18. It looks pretty recursive to
    me. The problem he's having does not, itself, involve recursion, but
    it's occurring in a recursive routine, and it's occurring because he
    inserted code intended to produce output that might help him gain an
    understanding of how the recursion works.
     
    James Kuyper, Jul 9, 2013
    #3
  4. rrice899

    osmium Guest

    :

    I had the same problem. With the total lack of indentation (as it was
    presented to me) I couldn't even tell the intent.
     
    osmium, Jul 9, 2013
    #4
  5. rrice899

    Ike Naar Guest

    Apart from the problems that have been mentioned elsethread, have
    a look at the variable 'indent': it is a local variable inside the
    function 'towers', where it is initialized to 10.
    It doesn't matter how deep the level of recursion is, in every call
    to 'towers' this local variable 'indent' will have the value 10
    where it is used.

    Try to do things one by one; for instance, start by printing 'indent'
    as a number along with the "Move disk" message, and leave the string
    handling for later, when you have made sure that 'indent' has the
    desired value.

    Please fix the indentation of the program text itself.
    If the program text is hard to read, it will be more difficult
    to get things right.
    that
     
    Ike Naar, Jul 9, 2013
    #5
  6. My guess is that the indentation *is* probably OK in his native environment
    (IDE or maybe just vi or some other editor), but that it got whacked out
    when he posted - probably using some whacky interface like "Google Groups"
    or something else whacky.

    --
    "The anti-regulation business ethos is based on the charmingly naive notion
    that people will not do unspeakable things for money." - Dana Carpender

    Quoted by Paul Ciszek (pciszek at panix dot com). But what I want to know
    is why is this diet/low-carb food author doing making pithy political/economic
    statements?

    Nevertheless, the above quote is dead-on, because, the thing is - business
    in one breath tells us they don't need to be regulated (which is to say:
    that they can morally self-regulate), then in the next breath tells us that
    corporations are amoral entities which have no obligations to anyone except
    their officers and shareholders, then in the next breath they tell us they
    don't need to be regulated (that they can morally self-regulate) ...
     
    Kenny McCormack, Jul 9, 2013
    #6
  7. rrice899

    James Kuyper Guest

    Recursion is the context of this issue; it isn't the issue itself. No
    one has suggested otherwise.
     
    James Kuyper, Jul 9, 2013
    #7
  8. rrice899

    osmium Guest

    Telling someone who is leaning C that his problem is not with recursion,
    sounds about as useful as telling someone who has never looked under the
    hood of a car that his problem is most assuredly not with the Johnson bar.
     
    osmium, Jul 9, 2013
    #8
  9. Formatting is important.

    For English text in articles you post here, it's best to keep your lines
    shorter than 80 columns; 72 is better. Usenet is not the web; not all
    newsreaders wrap very long lines for readability. (Mine, for example,
    wraps long lines, but not at word boundaries.)

    For C code, proper indentation is very important if you expect anyone to
    read it. See if your system has a code formatting program like
    "indent", or if your editor will automatically format code for you.

    Here's your program (with the errors left in place) with proper
    indentation (not every agrees on just how C code should be indented, but
    there's near universal agreement that it should be indended
    consistently):

    #include <stdio.h>
    #include <string.h>

    void towers(int, char, char, char);

    void towers(int n, char frompeg, char topeg, char auxpeg) {
    int indent = 10;
    int i;
    char *str = "";
    {
    for(i = 0; i < indent; i++) {
    char *strcat(str, "-");
    }
    if(n > 0) {
    towers(n-1, frompeg, auxpeg, topeg);
    printf("\nMove disk %d from peg %c to peg %c\n",
    n, frompeg, topeg);
    indent = indent +1;
    printf("%c\n", *str);
    towers(n-1, auxpeg, topeg, frompeg);
    indent = indent + 1;
    }
    }
    }

    int main() {
    int n = 2;
    printf("The tower of Hanoi involves the moves: \n\n");
    towers(n, 'A', 'C', 'B');
    return 0;
    }

    One thing that this reveals is that one of the sets of curly braces in
    your towers() function (the `{` following `char *str = "";`, and the
    corresponding `}`) are (harmless but) unnecessary.
     
    Keith Thompson, Jul 10, 2013
    #9
  10. For someone new to C, but experienced in other languages, that
    isn't much of a hint. Note, for example, that in Java you can
    easily concatenate strings without worrying about the size of
    anything. (Other than available memory.) It is pretty usual in
    Java to initialize a String with "", then concatenate to it
    inside a loop.

    I suppose the OP should read the man page for strcat() more
    carefully.

    -- glen
     
    glen herrmannsfeldt, Jul 10, 2013
    #10
  11. rrice899

    rrice899 Guest

    Thank you very much James. Your suggestions helped a great deal. The output now prints dashes of various lengths for each recursion call.
    To Keith regarding indenting: I will follow your directions.
    I assure everyone this is not homework. I'm learning C from a book and an IDE called Code::Blocks.
    My corrected code is below with James' suggestions on line 4 and 11.
    #include <stdio.h>
    #include <string.h>
    #define LONG_ENOUGH 256
    char str[LONG_ENOUGH]; //James Kuyper
    void towers(int, char, char, char);
    void towers(int n, char frompeg, char topeg, char auxpeg){
    int indent = 10;
    int i;
    {
    for(i = 0; i < indent; i++)
    strcat(str, "-"); //James Kuyper
    if(n > 0){
    towers(n-1, frompeg, auxpeg, topeg);
    printf("\nMove disk %d from peg %c to peg %c\n", n, frompeg, topeg);
    printf("%s\n", str);
    towers(n-1, auxpeg, topeg, frompeg);
    }
    }
    }
    int main(){
    int n = 2;
    printf("The tower of Hanoi involves the moves: \n\n");
    towers(n, 'A', 'C', 'B');
    return 0;
    }
    OUTPUT
    The tower of Hanoi involves the moves:


    Move disk 1 from peg A to peg B
     
    rrice899, Jul 10, 2013
    #11
  12. My suggest was that you (a) keep your lines of text shorter than 80
    columns, and (b) properly indent your C code. You're still doing
    neither.
    [...]

    Sometimes if you use tab characters to indent your code, they can be
    lost when posting to Usenet, depending on how you post. Or is your code
    really left-justified like that?
     
    Keith Thompson, Jul 10, 2013
    #12
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.