please discuss recursive calls, program provided.

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

  1. gdotone

    gdotone 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 */


    /* 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 */
    } /* 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.


    gdotone, Sep 8, 2013
    1. Advertisements

  2. gdotone

    Paul N Guest

    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 N, Sep 8, 2013
    1. Advertisements

  3. gdotone

    Eric Sosman Guest

    Aside: You probably mean "Deitel and Deitel".
    Aside: The code actually uses fgets(), not gets(). That's
    good -- never use gets(), not ever.
    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

    '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).
    This might become

    if (sPtr[0] == '\n' || sPtr[0] == '\0')
    That's strange. I'd expect the screen to look something like

    gdotone> fig08_13
    Enter a line of text

    The line printed backward is:


    .... but your mileage may vary.
    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, Sep 8, 2013
  4. gdotone

    gdotone Guest

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

    /* 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
    that was a line number. it there do to my editing effort.

    fgets ( sentence, 80, stdin );
    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)
    when reverse is called
    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


    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
    gdotone, Sep 9, 2013
  5. On Sun, 8 Sep 2013 13:41:04 -0700 (PDT), wrote:

    Since sPtr is defined as a pointer, you can simplify (at least in
    terms of typing) the expression &sPtr[1] to the more conventional
    You could also use *sPtr for sPtr[0].
    Barry Schwarz, Sep 9, 2013
  6. gdotone

    Eric Sosman Guest

    Ahh, good old computers! What would we do without them?
    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.
    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-
    I liked Paul N's response: Direct and to the point.
    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, Sep 9, 2013
  7. gdotone

    gdotone Guest

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

    gdotone, Sep 9, 2013
  8. gdotone

    Hans Vlems Guest

    Op zondag 8 september 2013 22:41:04 UTC+2 schreef :
    Perhaps this simplified version of reverse will help you:

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

    Hans Vlems, Sep 9, 2013
  9. gdotone

    Hans Vlems Guest

    Op maandag 9 september 2013 12:37:41 UTC+2 schreef Richard Damon:
    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
  10. gdotone

    blmblm Guest

    [ snip ]

    [ snip ]

    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') {

    int main(void) {
    printf("enter a line of text:\n");
    return 0;
    blmblm, Sep 9, 2013
  11. 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
  12. gdotone

    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
    However, if you insist on continuing to use Google Groups, please remove
    the spurious extra spacing it inserts in quoted material.

    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
  13. (snip)
    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
    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
  14. gdotone

    Paul N Guest

    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
  15. gdotone

    osmium Guest


    <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.
    osmium, Sep 9, 2013
  16. (snip, I wrote)
    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
  17. .... in C. In languages that use it the basic control structure it
    becomes quite natural to use it for linear solutions.
    All loops are "real recursive algorithms", but not all recursive
    patterns correspond to loops.
    Not at all. You can implement a Fibonacci function using recursion that
    is not horribly inefficient. You can do it even in C.
    Ben Bacarisse, Sep 10, 2013
  18. gdotone

    Joe Pfeiffer Guest

    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
  19. gdotone

    osmium Guest

    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
  20. 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
    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.