please discuss recursive calls, program provided.

Discussion in 'C Programming' started by gdotone@gmail.com, Sep 8, 2013.

  1. Guest

    From Dietel and Dietel

    /* Fig. 8.13: fig08_13.c
    Using gets and putchar */
    #include <stdio.h>

    void reverse( const char * const sPtr ); /* prototype */ 6

    int main( void )
    {
    char sentence[ 80 ]; /* create char array */

    printf( "Enter a line of text:\n" ); 12

    fgets ( sentence, 80, stdin );

    printf( "\nThe line printed backward is:\n" );
    reverse( sentence );

    return 0; /* indicates successful termination */

    }/*endmain*/

    /* recursively outputs characters in string in reverse order */
    void reverse( const char * const sPtr )
    {
    /* if end of the string */
    if ( sPtr[ 0 ] == '\0' ) { /* base case */
    return;
    } /* end if */
    else { /* if not end of the string */
    reverse( &sPtr[ 1 ] ); /* recursion step */
    putchar( sPtr[ 0 ] ); /* use putchar to display character */
    } /* end else */

    } /* end function reverse */

    I don't think I have a good grasp of when putchar( sPtr[ 0 ] ); get called.

    recursively. the function reverse is called until the base case if found.
    The pointer sPtr points to '\0'.

    Let the sentence be Hello.
    I get back olleH.

    When is putchar called.

    Thanks,

    g.
    , Sep 8, 2013
    #1
    1. Advertising

  2. Paul N Guest

    On Sunday, 8 September 2013 21:41:04 UTC+1, wrote:
    > From Dietel and Dietel
    >
    >
    >
    > /* Fig. 8.13: fig08_13.c
    >
    > Using gets and putchar */
    >
    > #include <stdio.h>
    >
    >
    >
    > void reverse( const char * const sPtr ); /* prototype */ 6
    >
    >
    >
    > int main( void )
    >
    > {
    >
    > char sentence[ 80 ]; /* create char array */
    >
    >
    >
    > printf( "Enter a line of text:\n" ); 12
    >
    >
    >
    > fgets ( sentence, 80, stdin );
    >
    >
    >
    > printf( "\nThe line printed backward is:\n" );
    >
    > reverse( sentence );
    >
    >
    >
    > return 0; /* indicates successful termination */
    >
    >
    >
    > }/*endmain*/
    >
    >
    >
    > /* recursively outputs characters in string in reverse order */
    >
    > void reverse( const char * const sPtr )
    >
    > {
    >
    > /* if end of the string */
    >
    > if ( sPtr[ 0 ] == '\0' ) { /* base case */
    >
    > return;
    >
    > } /* end if */
    >
    > else { /* if not end of the string */
    >
    > reverse( &sPtr[ 1 ] ); /* recursion step */
    >
    > putchar( sPtr[ 0 ] ); /* use putchar to display character */
    >
    > } /* end else */
    >
    >
    >
    > } /* end function reverse */
    >
    >
    >
    > I don't think I have a good grasp of when putchar( sPtr[ 0 ] ); get called.
    >
    >
    >
    > recursively. the function reverse is called until the base case if found.
    >
    > The pointer sPtr points to '\0'.
    >
    >
    >
    > Let the sentence be Hello.
    >
    > I get back olleH.
    >
    >
    >
    > When is putchar called.
    >
    >
    >
    > Thanks,
    >
    >
    >
    > g.


    It might help to consider a shorter example. Suppose you call reverse("abc"). The function reverse will, if the string is not empty, call itself on the string begining with the second character, then print the first one. So in effect we get:

    reverse("bc"); putchar('a');

    Buit what does reverse("bc") do? Well, it too calls reverse, then prints its first character. So we now have:

    reverse("c"); putchar('b'); putchar('a');

    And again:

    reverse(""); putchar('c'); putchar('b'); putchar('a');

    And now we are calling reverse with an empty string, so nothing happens, leaving us with:

    putchar('c'); putchar('b'); putchar('a');

    In case it's not clear - in C a string is a succession of characters endingwith a 0. So if you want another string that starts part-way along your first string and goes all the way to the end of it, you can simply use a pointer to the start position in the original string. If instead you want a string that stops before the end of the old one, you will need to allocate some space and build a copy of the relevant part of the first string.

    Incidentally, you may need to print a \n at the end to get the last line toprint properly; you have a spare "6" and "12" in your code; and the comment is wrong as you don't use "gets".

    Hope that helps.
    Paul.
    Paul N, Sep 8, 2013
    #2
    1. Advertising

  3. Eric Sosman Guest

    On 9/8/2013 4:41 PM, wrote:
    > From Dietel and Dietel


    Aside: You probably mean "Deitel and Deitel".

    > /* Fig. 8.13: fig08_13.c
    > Using gets and putchar */


    Aside: The code actually uses fgets(), not gets(). That's
    good -- never use gets(), not ever.

    > #include <stdio.h>
    >
    > void reverse( const char * const sPtr ); /* prototype */ 6
    >
    > int main( void )
    > {
    > char sentence[ 80 ]; /* create char array */
    >
    > printf( "Enter a line of text:\n" ); 12


    "12"?

    > fgets ( sentence, 80, stdin );


    I've said "never use gets()" and I stand by that advice,
    but there *is* one tiny thing gets() does for you that fgets()
    does not: It removes the '\n' character from the end of the
    line it stores. That is, gets() would have given you the six
    characters

    'H', 'e', 'l', 'l', 'o', '\0'

    but fgets() will store *seven* characters

    'H', 'e', 'l', 'l', 'o', '\n', '\0'

    This is sometimes a nuisance, as in your program: When you
    print the string in reverse the first character printed will
    be the '\n', which you probably don't want.

    One thing you can do is obliterate the '\n' character,
    which requires just a little care because there might not be
    one (if fgets() gets to the end of your array before seeing
    an end-of-line, it just stores what it's got and goes no
    further). Here are two safe ways to obliterate:

    char *newline = strchr(sentence, '\n');
    if (newline != NULL)
    *newline = '\0';

    or, making use of a less familiar but no less useful function:

    sentence[ strcspn(sentence, "\n") ] = '\0';

    The other thing that's often done is to arrange to ignore
    the '\n' when you encounter it when processing the input. Many
    programs already ignore at least some spaces and tabs and things,
    and it's straightforward to include '\n' among the ignored. In
    your program the reverse() function recognizes '\0' as the end
    of the line; you might have it treat a '\n' the same way (make
    sure to test for both: As explained above, the '\n' might not
    be present).

    > printf( "\nThe line printed backward is:\n" );
    > reverse( sentence );
    >
    > return 0; /* indicates successful termination */
    >
    > }/*endmain*/
    >
    > /* recursively outputs characters in string in reverse order */
    > void reverse( const char * const sPtr )
    > {
    > /* if end of the string */
    > if ( sPtr[ 0 ] == '\0' ) { /* base case */


    This might become

    if (sPtr[0] == '\n' || sPtr[0] == '\0')

    > return;
    > } /* end if */
    > else { /* if not end of the string */
    > reverse( &sPtr[ 1 ] ); /* recursion step */
    > putchar( sPtr[ 0 ] ); /* use putchar to display character */
    > } /* end else */
    >
    > } /* end function reverse */
    >
    > I don't think I have a good grasp of when putchar( sPtr[ 0 ] ); get called.
    >
    > recursively. the function reverse is called until the base case if found.
    > The pointer sPtr points to '\0'.
    >
    > Let the sentence be Hello.
    > I get back olleH.


    That's strange. I'd expect the screen to look something like

    gdotone> fig08_13
    Enter a line of text
    Hello

    The line printed backward is:

    olleHgdotone>

    .... but your mileage may vary.

    > When is putchar called.


    In the "else" part of the "if" in reverse(), after printing
    the reverse of the right-hand part of the string.

    Aside: Reversing a string isn't a problem that really calls
    out for a recursive solution; an iterative method would be much
    more direct. I suppose D&D are using it not as a way to reverse
    a string, but as a way to introduce recursion without tying the
    student up in a lot of complications -- I have to admit it's a
    better problem than the usual Truly Awful exercise of computing
    Fibonacci numbers! Still, the typical reason for a recursive
    approach is when the "splitting" step produces two or more sub-
    problems to be solved recursively. Exploring a maze, for example:

    void explore (Junction junction) {
    // Here I am at a junction where N corridors branch
    for (int i = 0; i < junction.corridorCount; ++i) {
    Corridor corridor = junction.corridor;
    if (! corridor.explored) {
    corridor.explored = true;
    explore (corridor.junctionAtOppositeEnd);
    }
    }
    }

    The sub-problems are to explore the maze starting from the other
    end of each of the N branching corridors; the "super-problem" is
    to explore the maze starting from `junction'. Now to explore
    the entire (connected portion of) the maze, just clear all the
    `explored' flags and call explore(anyJunctionYouCareToStartFrom);
    the recursion will follow all possible leads from that point on.

    --
    Eric Sosman
    d
    Eric Sosman, Sep 8, 2013
    #3
  4. Guest

    On Sunday, September 8, 2013 5:39:18 PM UTC-4, Eric Sosman wrote:
    > On 9/8/2013 4:41 PM, wrote:
    >
    > > From Dietel and Diesel

    >
    > Aside: You probably mean "Deitel and Deitel".


    yes, it should be Deitel and Deitel.
    my computer corrected the spelling.

    /* Fig. 8.13: fig08_13.c
    Using gets and putchar */

    > Aside: The code actually uses fgets(), not gets(). That's


    #include <stdio.h>

    void reverse( const char * const sPtr ); /* prototype */ 6

    int main( void )
    {
    char sentence[ 80 ]; /* create char array */
    printf( "Enter a line of text:\n" ); 12

    > "12"?


    that was a line number. it there do to my editing effort.

    fgets ( sentence, 80, stdin );
    >
    >I've said "never use gets()" and I stand by that advice,
    > but there *is* one tiny thing gets() does for you that fgets()
    > does not: It removes the '\n' character from the end of the
    > line it stores. That is, gets() would have given you the six
    > characters


    > 'H', 'e', 'l', 'l', 'o', '\0'


    The chapter is about: "Standard Input/Output Library Function"

    so, i think it's more about showing the use of the functions,
    but thanks for the incite of correct usage.

    fibonacci is discussed, but i understood the code there.

    Is this like pushing these characters onto a stack?
    so, as i work down the stack the next line is executed, the putchar()?

    my thought was that it actually move down the string of characters one character at
    a time, i mean ...

    let's say sentence is "abc\0" (following Paul"s thought, he's right it's shorter)
    so
    when reverse is called
    sPtr->abc\0
    the else statements are executed
    so reverse is called (starting at the address of the second char)
    sPtr -> bc\0
    the else statements are executed
    so reverse is called
    sPtr -> c\0
    the else statements are executed
    so reverse is called
    sPtr ->\0
    now this the base case so we work back down the stack
    ( i may not be using terminology stack correctly here)

    moving back down (so to speak)
    sPtr[0] ->c so execute putchar[sPtr[0]) that prints c
    still moving back down
    sPtr-> b so execute putchar ... that prints b
    still moving back down
    sPtr-> a so execute putchar ... that print a

    cba

    ok that said, that would mean that when a recursive function is called
    as it works it way back, after it's base case has been found it should start
    execution where it left off which would be after the recursive() call.

    Does that make sense?

    Ok, i guess that is what you said Paul. thanks
    , Sep 9, 2013
    #4
  5. On Sun, 8 Sep 2013 13:41:04 -0700 (PDT), wrote:

    <snip>

    >/* recursively outputs characters in string in reverse order */
    >void reverse( const char * const sPtr )
    >{
    > /* if end of the string */
    > if ( sPtr[ 0 ] == '\0' ) { /* base case */
    > return;
    > } /* end if */
    > else { /* if not end of the string */
    > reverse( &sPtr[ 1 ] ); /* recursion step */


    Since sPtr is defined as a pointer, you can simplify (at least in
    terms of typing) the expression &sPtr[1] to the more conventional
    sPtr+1.

    > putchar( sPtr[ 0 ] ); /* use putchar to display character */


    You could also use *sPtr for sPtr[0].

    > } /* end else */
    >
    >} /* end function reverse */


    --
    Remove del for email
    Barry Schwarz, Sep 9, 2013
    #5
  6. Eric Sosman Guest

    On 9/8/2013 7:15 PM, wrote:
    > On Sunday, September 8, 2013 5:39:18 PM UTC-4, Eric Sosman wrote:
    >> On 9/8/2013 4:41 PM, wrote:
    >>
    >>> From Dietel and Diesel

    >>
    >> Aside: You probably mean "Deitel and Deitel".

    >
    > yes, it should be Deitel and Deitel.
    > my computer corrected the spelling.


    Ahh, good old computers! What would we do without them?

    > /* Fig. 8.13: fig08_13.c
    > Using gets and putchar */
    >
    >> Aside: The code actually uses fgets(), not gets(). That's

    >
    > #include <stdio.h>
    >
    > void reverse( const char * const sPtr ); /* prototype */ 6
    >
    > int main( void )
    > {
    > char sentence[ 80 ]; /* create char array */
    > printf( "Enter a line of text:\n" ); 12
    >
    >> "12"?

    >
    > that was a line number. it there do to my editing effort.


    For future reference: When you post code that's giving you
    trouble, post *exactly* the troublesome code. Don't re-type it,
    don't paraphrase it, copy and paste directly from your code editor.
    That way you'll be spared the embarrassment of posting some silly
    typo and reading forty-leven replies that point it out instead of
    addressing the actual problem. "We can't debug what we can't see,"
    so make sure we see what needs debugging and not something else.

    > fgets ( sentence, 80, stdin );
    >>
    >> I've said "never use gets()" and I stand by that advice,
    >> but there *is* one tiny thing gets() does for you that fgets()
    >> does not: It removes the '\n' character from the end of the
    >> line it stores. That is, gets() would have given you the six
    >> characters

    >
    >> 'H', 'e', 'l', 'l', 'o', '\0'

    >
    > The chapter is about: "Standard Input/Output Library Function"
    >
    > so, i think it's more about showing the use of the functions,
    > but thanks for the incite of correct usage.
    >
    > fibonacci is discussed, but i understood the code there.
    >
    > Is this like pushing these characters onto a stack?
    > so, as i work down the stack the next line is executed, the putchar()?


    Sort of. It may be more useful to think of it as pushing a
    "state" or "situation" on a stack. In the recursive call, you're
    saying "Go off and perform your sub-task, then come back *here*
    and I'll take care of the rest." Each stack entry is a "*here*",
    a "Now, then, where was I?" to be resumed after solving the sub-
    problem.

    > my thought was that it actually move down the string of characters one character at
    > a time, i mean ...
    >
    > let's say sentence is "abc\0" (following Paul"s thought, he's right it's shorter)


    I liked Paul N's response: Direct and to the point.

    > so
    > when reverse is called
    > sPtr->abc\0
    > the else statements are executed
    > so reverse is called (starting at the address of the second char)
    > sPtr -> bc\0
    > the else statements are executed
    > so reverse is called
    > sPtr -> c\0
    > the else statements are executed
    > so reverse is called
    > sPtr ->\0
    > now this the base case so we work back down the stack
    > ( i may not be using terminology stack correctly here)
    >
    > moving back down (so to speak)
    > sPtr[0] ->c so execute putchar[sPtr[0]) that prints c
    > still moving back down
    > sPtr-> b so execute putchar ... that prints b
    > still moving back down
    > sPtr-> a so execute putchar ... that print a
    >
    > cba
    >
    > ok that said, that would mean that when a recursive function is called
    > as it works it way back, after it's base case has been found it should start
    > execution where it left off which would be after the recursive() call.
    >
    > Does that make sense?


    Yes, that's exactly It. No different from an ordinary function
    call, really: You say "Computer! Go compute this square root, then
    come back *here* with the answer" -- and the computer remembers where
    "*here*" is, so it knows where to resume after the square root is
    found. This is exactly what happens in a recursive call, too, the
    only mind-bending part being that the function calls itself, and when
    the inner call finishes it resumes where it was called from -- which
    is, once again, in itself.

    Well, when a function assigned to perform Job X calls itself,
    isn't that an infinite loop? Yes, it could be -- of course, your
    computer would run out of memory to store an infinite number of
    "*here*" places where it should resume, so the infinite loop would
    be cut short by the computer's finite resources. But in a
    "practical" recursion the function told to do X does not call
    itself to do X, but to do some smaller sub-task X.1 (or set of
    sub-tasks X.1, X.2, ...) Eventually you arrive at a "base case"
    where task X.1.3...1 is "small enough" to be solved directly without
    further recursion. The lowest-level invocation solves its sub-sub-
    sub-problem and returns to "*here*" in the calling invocation,
    exactly as if it had provided a square root for a caller that's
    solving a quadratic.

    At a theoretical level, recursion and iteration are equivalent:
    Any loop can be expressed as a recursion, any recursion can be
    expressed as a loop. The choice of which "framework" to use should
    be driven by the nature of the problem and by the capabilities of
    the programming language. As I wrote earlier, reversing a string
    in C does not strike me as a problem best suited for a recursive
    approach -- still, it *can* be done, and if it helps you understand
    recursion without dragging in a bunch of topics you neither know nor
    care about, that's all to the good.

    --
    Eric Sosman
    d
    Eric Sosman, Sep 9, 2013
    #6
  7. Guest

    On Sunday, September 8, 2013 9:45:08 PM UTC-4, Eric Sosman wrote:

    > Well, when a function assigned to perform Job X calls itself,
    > isn't that an infinite loop? Yes, it could be -- of course, your
    > computer would run out of memory to store an infinite number of
    > "*here*" places where it should resume, so the infinite loop would
    > be cut short by the computer's finite resources. But in a
    > "practical" recursion the function told to do X does not call
    > itself to do X, but to do some smaller sub-task X.1 (or set of
    > sub-tasks X.1, X.2, ...) Eventually you arrive at a "base case"
    > where task X.1.3...1 is "small enough" to be solved directly without
    > further recursion. The lowest-level invocation solves its sub-sub-
    > sub-problem and returns to "*here*" in the calling invocation,
    > exactly as if it had provided a square root for a caller that's
    > solving a quadratic.


    your explanation was exactly what i needed to drive the point home.
    of course, the function call, recursive though it is, would then come
    back to the point in the program after the function left off and
    continue its work. man! i don't know how that point blew by me. Thanks for
    the patient explanation.

    in the fibonacci example, in the text, there is no code after the function call.

    I think i've got it, now. plus using a string to do this, recursion, may have helped to
    throw me for a loop. :)

    your explanation makes absolute sense.

    > At a theoretical level, recursion and iteration are equivalent:
    > Any loop can be expressed as a recursion, any recursion can be
    > expressed as a loop. The choice of which "framework" to use should
    > be driven by the nature of the problem and by the capabilities of
    > the programming language. As I wrote earlier, reversing a string
    > in C does not strike me as a problem best suited for a recursive
    > approach -- still, it *can* be done, and if it helps you understand
    > recursion without dragging in a bunch of topics you neither know nor
    > care about, that's all to the good.


    I'm going to look for some exercises that require recursion so i can
    practice the idea. (when to use recursion...the problems that lend themselves to
    recursion and changing recursion to iteration)

    Thanks Eric, perfect explanation for me...

    g.
    , Sep 9, 2013
    #7
  8. Hans Vlems Guest

    Op zondag 8 september 2013 22:41:04 UTC+2 schreef :
    > From Dietel and Dietel
    >
    >

    [snip]
    >
    > Let the sentence be Hello.
    >
    > I get back olleH.
    >
    >
    >
    > When is putchar called.
    >
    >
    >
    > Thanks,
    >
    >
    >
    > g.


    Perhaps this simplified version of reverse will help you:

    void reverse(const char * const sPtr)
    {
    if (sPtr[0]) reverse(&sPtr[1]);
    putchar(sPtr[0]);
    }

    Hans
    Hans Vlems, Sep 9, 2013
    #8
  9. Hans Vlems Guest

    Op maandag 9 september 2013 12:37:41 UTC+2 schreef Richard Damon:
    > On 9/9/13 4:50 AM, Hans Vlems wrote:
    >
    >
    >
    > > Perhaps this simplified version of reverse will help you:

    >
    > >

    >
    > > void reverse(const char * const sPtr)

    >
    > > {

    >
    > > if (sPtr[0]) reverse(&sPtr[1]);

    >
    > > putchar(sPtr[0]);

    >
    > > }

    >
    > >

    >
    > > Hans

    >
    > >

    >
    >
    >
    > The one problem is that this code is significantly different then the
    >
    > original, and has a bug introduced (you are going to output the null
    >
    > that was at the end of the string out first). If you are going to
    >
    > rewrite it, is should be like:
    >
    >
    >
    > void reverse(const char * const sPtr)
    >
    > {
    >
    > if (sPtr[0])
    >
    > {
    >
    > reverse(&sPtr[1]);
    >
    > putchar(sPtr[0]);
    >
    > }
    >
    > }
    >
    >
    >
    >
    >
    > but I don't think this would help that much in the comprehension of the
    >
    > recursion, if the problem was not understanding how recursive calls work
    >
    > (being exactly the same as non-recursive calls).


    Of course the code is different, otherwise it wouldn't help at all.
    The point was to simplify the recursion method and possibly assist in understanding the technique.
    Hans Vlems, Sep 9, 2013
    #9
  10. Guest

    In article <l0iqq8$lqe$>,
    Eric Sosman <> wrote:
    > On 9/8/2013 4:41 PM, wrote:


    [ snip ]

    > > /* recursively outputs characters in string in reverse order */
    > > void reverse( const char * const sPtr )
    > > {
    > > /* if end of the string */
    > > if ( sPtr[ 0 ] == '\0' ) { /* base case */

    >
    > This might become
    >
    > if (sPtr[0] == '\n' || sPtr[0] == '\0')
    >
    > > return;
    > > } /* end if */
    > > else { /* if not end of the string */
    > > reverse( &sPtr[ 1 ] ); /* recursion step */
    > > putchar( sPtr[ 0 ] ); /* use putchar to display character */
    > > } /* end else */
    > >
    > > } /* end function reverse */



    [ snip ]


    > Aside: Reversing a string isn't a problem that really calls
    > out for a recursive solution; an iterative method would be much
    > more direct. I suppose D&D are using it not as a way to reverse
    > a string, but as a way to introduce recursion without tying the
    > student up in a lot of complications -- I have to admit it's a
    > better problem than the usual Truly Awful exercise of computing
    > Fibonacci numbers! Still, the typical reason for a recursive
    > approach is when the "splitting" step produces two or more sub-
    > problems to be solved recursively. Exploring a maze, for example:
    >
    > void explore (Junction junction) {
    > // Here I am at a junction where N corridors branch
    > for (int i = 0; i < junction.corridorCount; ++i) {
    > Corridor corridor = junction.corridor;
    > if (! corridor.explored) {
    > corridor.explored = true;
    > explore (corridor.junctionAtOppositeEnd);
    > }
    > }
    > }
    >
    > The sub-problems are to explore the maze starting from the other
    > end of each of the N branching corridors; the "super-problem" is
    > to explore the maze starting from `junction'. Now to explore
    > the entire (connected portion of) the maze, just clear all the
    > `explored' flags and call explore(anyJunctionYouCareToStartFrom);
    > the recursion will follow all possible leads from that point on.
    >



    I'll agree that the usefulness of recursion is (often?) better
    illustrated by problems in which the solution is generated using
    more than one recursive call, your example being one such.


    But the example quoted by the OP .... An iterative solution is
    indeed more direct. However, one can use recursion to avoid the
    maybe-problem of deciding how big to make the buffer for fgets(),
    as shown in the revision below.

    (Not an original idea, but one I thought was clever when it was first
    shown to me some years ago.)

    One might reasonably claim that the overhead incurred by recursion
    easily swamps any advantage, but still -- kind of clever?


    #include <stdio.h>

    /*
    * read characters until end-of-line and print in reverse order
    * does not print end-of-line
    */
    void reverse(void) {
    int ch;
    if ((ch = getchar()) != '\n') {
    reverse();
    putchar(ch);
    }
    }

    int main(void) {
    printf("enter a line of text:\n");
    printf("reversed:\n");
    reverse();
    putchar('\n');
    return 0;
    }

    --
    B. L. Massingill
    ObDisclaimer: I don't speak for my employers; they return the favor.
    , Sep 9, 2013
    #10
  11. On Monday, September 9, 2013 2:45:08 AM UTC+1, Eric Sosman wrote:
    > On 9/8/2013 7:15 PM, wrote:
    >
    > At a theoretical level, recursion and iteration are equivalent:
    > Any loop can be expressed as a recursion, any recursion can be
    > expressed as a loop. The choice of which "framework" to use should
    > be driven by the nature of the problem and by the capabilities of
    > the programming language. As I wrote earlier, reversing a string
    > in C does not strike me as a problem best suited for a recursive
    > approach -- still, it *can* be done, and if it helps you understand
    > recursion without dragging in a bunch of topics you neither know nor
    > care about, that's all to the good.
    >

    There's something called the lambda calculus which is theoretically very
    important - basically all possible calculations can be done by passing
    true or nil arguments to a recursive function which uses the parameters
    as state. But it's not of much use for practical, everyday programming.

    In C and most procedural languages, recursion is mainly used when operating
    on data which is tree-like. Trees arise all the time, both in obvious
    contexts like directories or genealogies, and in the less obvious like
    compression and expression parsing.

    You can argue about whether it's best to teach recursion using a problem
    where you'd normally use recursion for real, or on a problem where
    you generally wouldn't, like string reversal.
    Malcolm McLean, Sep 9, 2013
    #11
  12. James Kuyper Guest

    Note: Google Groups has a defect that Google is unwilling to fix, which
    causes quoted material to be double-spaced. There are better news
    readers out there, such as Mozilla Thunderbird, and good free news
    servers that you can use with them, such as eternal-september.org.
    However, if you insist on continuing to use Google Groups, please remove
    the spurious extra spacing it inserts in quoted material.

    On 09/09/2013 08:10 AM, Hans Vlems wrote:
    > Op maandag 9 september 2013 12:37:41 UTC+2 schreef Richard Damon:
    >> On 9/9/13 4:50 AM, Hans Vlems wrote:
    >>
    >>> Perhaps this simplified version of reverse will help you:
    >>>
    >>> void reverse(const char * const sPtr)
    >>> {
    >>> if (sPtr[0]) reverse(&sPtr[1]);
    >>> putchar(sPtr[0]);
    >>> }

    ....
    >> The one problem is that this code is significantly different then the
    >> original, and has a bug introduced (you are going to output the null
    >> that was at the end of the string out first). If you are going to
    >> rewrite it, is should be like:
    >>
    >> void reverse(const char * const sPtr)
    >> {
    >> if (sPtr[0])
    >> {
    >> reverse(&sPtr[1]);
    >> putchar(sPtr[0]);
    >> }
    >> }
    >>
    >> but I don't think this would help that much in the comprehension of the
    >> recursion, if the problem was not understanding how recursive calls work
    >> (being exactly the same as non-recursive calls).

    >
    > Of course the code is different, otherwise it wouldn't help at all.


    The code wouldn't be helpful unless it attempts to print out the null
    character that the original code correctly did not print out? I find
    that claim confusing. Richard Damon's version seems to me to be much
    more helpful than yours.
    James Kuyper, Sep 9, 2013
    #12
  13. Malcolm McLean <> wrote:

    (snip)

    > In C and most procedural languages, recursion is mainly used
    > when operating on data which is tree-like. Trees arise all
    > the time, both in obvious contexts like directories or
    > genealogies, and in the less obvious like compression
    > and expression parsing.


    Yes. For linear problems, such as linked lists, recursion is
    rarely the best solution. Even for real recursive algorithms,
    it is often more efficient, and not so much more work, to do
    it without using recursive calls. Quicksort is a favorite
    example.

    > You can argue about whether it's best to teach recursion using a
    > problem where you'd normally use recursion for real, or on
    > a problem where you generally wouldn't, like string reversal.


    I suppose one should explain up front that the problems are just
    examples. The favorite first recursion example is factorial, which
    is much easier to implement as a loop. Fibonacci is horribly
    inefficient as recursion, and easy to implement as a loop.

    -- glen
    glen herrmannsfeldt, Sep 9, 2013
    #13
  14. Paul N Guest

    On Monday, 9 September 2013 19:38:46 UTC+1, glen herrmannsfeldt wrote:
    > Malcolm McLean <> wrote:
    > > You can argue about whether it's best to teach recursion using a
    > > problem where you'd normally use recursion for real, or on
    > > a problem where you generally wouldn't, like string reversal.

    >
    > I suppose one should explain up front that the problems are just
    > examples. The favorite first recursion example is factorial, which
    > is much easier to implement as a loop. Fibonacci is horribly
    > inefficient as recursion, and easy to implement as a loop.


    I think one snag with the string reversal shown is that the function calls itself straight away, diving down the nested calls and only doing the actual work on the way back up again. This is not the most intuitive way of doing things, and this may be part of what confused the OP.
    Paul N, Sep 9, 2013
    #14
  15. osmium Guest

    "Paul N" wrote:

    <this weeks version of google atteempt to subvert Usenet>

    I think one snag with the string reversal shown is that the function calls
    itself straight away, diving down the nested calls and only doing the actual
    work on the way back up again. This is not the most intuitive way of doing
    things, and this may be part of what confused the OP.

    ----
    Sadly, it is often the case that a recursive solution does the work "on the
    way back up".
    osmium, Sep 9, 2013
    #15
  16. Paul N <> wrote:

    (snip, I wrote)

    >> I suppose one should explain up front that the problems are just
    >> examples. The favorite first recursion example is factorial, which
    >> is much easier to implement as a loop. Fibonacci is horribly
    >> inefficient as recursion, and easy to implement as a loop.


    > I think one snag with the string reversal shown is that the
    > function calls itself straight away, diving down the nested
    > calls and only doing the actual work on the way back up again.
    > This is not the most intuitive way of doing things, and
    > this may be part of what confused the OP.


    I suppose. One popular use for recursion is to deallocate a tree.

    A linked list isn't hard to deallocate in order, remembering the
    address for the next link while deallocating the current one.

    For a tree, it is much easier to deallocate from the leaf back
    to the root, so on the way back up, as you say. Just a little
    less intuitive.

    -- glen
    glen herrmannsfeldt, Sep 9, 2013
    #16
  17. glen herrmannsfeldt <> writes:

    > Malcolm McLean <> wrote:
    >
    > (snip)
    >
    >> In C and most procedural languages, recursion is mainly used
    >> when operating on data which is tree-like. Trees arise all
    >> the time, both in obvious contexts like directories or
    >> genealogies, and in the less obvious like compression
    >> and expression parsing.

    >
    > Yes. For linear problems, such as linked lists, recursion is
    > rarely the best solution.


    .... in C. In languages that use it the basic control structure it
    becomes quite natural to use it for linear solutions.

    > Even for real recursive algorithms,
    > it is often more efficient, and not so much more work, to do
    > it without using recursive calls. Quicksort is a favorite
    > example.


    All loops are "real recursive algorithms", but not all recursive
    patterns correspond to loops.

    >> You can argue about whether it's best to teach recursion using a
    >> problem where you'd normally use recursion for real, or on
    >> a problem where you generally wouldn't, like string reversal.

    >
    > I suppose one should explain up front that the problems are just
    > examples. The favorite first recursion example is factorial, which
    > is much easier to implement as a loop. Fibonacci is horribly
    > inefficient as recursion, and easy to implement as a loop.


    Not at all. You can implement a Fibonacci function using recursion that
    is not horribly inefficient. You can do it even in C.

    --
    Ben.
    Ben Bacarisse, Sep 10, 2013
    #17
  18. Joe Pfeiffer Guest

    Ben Bacarisse <> writes:

    > glen herrmannsfeldt <> writes:
    >
    >> Malcolm McLean <> wrote:
    >>
    >> I suppose one should explain up front that the problems are just
    >> examples. The favorite first recursion example is factorial, which
    >> is much easier to implement as a loop. Fibonacci is horribly
    >> inefficient as recursion, and easy to implement as a loop.

    >
    > Not at all. You can implement a Fibonacci function using recursion that
    > is not horribly inefficient. You can do it even in C.


    I would be very surprised to see a recursive Fibonacci that is both
    anywhere near as efficient as the obvious iterative solution and even
    remotely near as clear as either the obvious iterative solution or the
    obvious recursive solution.
    Joe Pfeiffer, Sep 10, 2013
    #18
  19. osmium Guest

    "David Brown" wrote:

    > Factorial is equally easy and clear as a loop or as recursion.


    They will be equally clear *after* you home some basic understanding of
    recursion. Recursion is, IMO, a pretty unnatural way of doing things. I
    can't think of much in daily life or thought that is analogous to recursion.
    The text book example is someone looking into a mirror which shows a second,
    reflected mirror.

    I agree that the Ackermann function is a good step for serious students of
    recursion (but my interest is not that great).
    osmium, Sep 10, 2013
    #19
  20. On Tuesday, September 10, 2013 1:26:13 PM UTC+1, osmium wrote:
    > "David Brown" wrote:
    >
    > > Factorial is equally easy and clear as a loop or as recursion.

    >
    > They will be equally clear *after* you home some basic understanding
    > of recursion. Recursion is, IMO, a pretty unnatural way of doing
    > things. I can't think of much in daily life or thought that is
    > analogous to recursion.
    >

    We're used to hierarchies. The Pope has cardinals below him who have bishops who have priests who have laypeople. So Pope is to cardinal
    as bishop is to priest.
    Malcolm McLean, Sep 10, 2013
    #20
    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. Jeff Epler
    Replies:
    0
    Views:
    488
    Jeff Epler
    Aug 20, 2004
  2. Jeff Epler
    Replies:
    0
    Views:
    438
    Jeff Epler
    Aug 23, 2004
  3. n00m
    Replies:
    12
    Views:
    1,098
  4. vamsi
    Replies:
    21
    Views:
    2,041
    Keith Thompson
    Mar 9, 2009
  5. G G
    Replies:
    20
    Views:
    381
    Tim Rentsch
    Sep 23, 2013
Loading...

Share This Page