please discuss recursive calls, program provided.

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

  1. I didn't know that one. Thanks.

    <snip>
     
    Ben Bacarisse, Sep 12, 2013
    #41
    1. Advertisements

  2. gdotone

    Joe Pfeiffer Guest

    No, because you mark pixels both above and below the current scan line
    for filling.
     
    Joe Pfeiffer, Sep 12, 2013
    #42
    1. Advertisements

  3. You keep two queues, the one going up and the one going down.
    When you're filling pixels from the queue, you only need to
    check in the opposite direction, because the pixel must
    have come from the south if it's the northwards queue and the
    north if its the southwards queue. However when you come to
    and end of a run of pixels, you need to check the east or
    the west positions. If they need to be filled, you have to
    extend the scanline and add to both queues.
    For an 8-connective fill you obviously need to check north-
    west, north-east and so on as well.
    So it saves a memory read.
     
    Malcolm McLean, Sep 13, 2013
    #43
  4. gdotone

    Seebs Guest

    I once saw someone use this for reading in a file, with one fgets()
    per line of input.

    -s
     
    Seebs, Sep 14, 2013
    #44
  5. gdotone

    blmblm Guest

    What does "this" mean, in context .... I adapted my example from a
    recursive solution to the somewhat-contrived problem of printing all
    lines from an input source in reverse order, which takes much the
    same approach as my little recursive function but applies itself to
    lines rather than characters. I'm not thinking off the top of my
    head how recursion would otherwise be useful for reading all lines ....

    What I did then ask myself was whether I could easily come up with a
    function that reads in a whole file/input and stores it, in forward
    order, in an array of just the right size, by making using of recursion.
    And indeed ....

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

    char* stdin_contents(size_t sz_prev) {
    char *p;
    int ch = getchar();
    if (ch == EOF) {
    p = malloc(sz_prev+1);
    ch = '\0';
    }
    else {
    p = stdin_contents(sz_prev+1);
    }
    if (p != NULL) {
    p[sz_prev] = ch;
    }
    return p;
    }

    int main(void) {
    char* contents = stdin_contents(0);
    if (contents == NULL) {
    printf("could not allocate memory\n");
    return 1;
    }
    printf("%d characters read\n", strlen(contents));
    printf("%s", contents);
    return 0;
    }

    Not practical in any context I can think of, but entertaining?
     
    blmblm, Sep 15, 2013
    #45
  6. gdotone

    Seebs Guest

    It didn't seem to me that it was, but that was what they did. Basically, it
    was an input processor which was supposed to process each line, so it was a
    loop roughly to the effect of:

    do_next_line() {
    fgets(static_buffer, size);
    /* do stuff with static_buffer */
    do_next_line();
    }

    -s
     
    Seebs, Sep 19, 2013
    #46
  7. gdotone

    blmblm Guest


    Ah, okay. I interpreted it as "recursion used to avoid the
    maybe-problem of deciding ...." and didn't understand. But ....:


    "Ah, okay" again. I guess someone who *really* likes recursion
    might find this more natural than a loop; other than that, yeah,
    "why?" I guess if the compiler is smart enough about optimizing
    tail recursion the comeback could be "why not?"
     
    blmblm, Sep 19, 2013
    #47
  8. gdotone

    Tim Rentsch Guest

    There's a two-component version based on d'Ocagne's identity.
    (I learned the technique years ago but just learned the name
    of the identity.) That identity is:

    f(2n) = f(n) * (f(n+1) + f(n-1))

    The idea is that if we have the pair ( f(n-1), f(n) ), we can
    calculate either ( f(2n-1), f(2n) ) or ( f(2n), f(2n+1) ),
    according to the binary decomposition of the input argument.
    Based on the above identity, and using a for f(n-1) b for f(n),
    the formulas are:

    f(2n) = 2*a*b + b*b
    f(2n-1) = f(2n) - f(2n-2) = a*a + b*b
    f(2n+1) = f(2n-1) + f(2n) = a*a + 2*a*b + 2*b*b

    It's pretty easy to write a recursive formulation using these
    identities, but a straightforward definition is kind of klunky.
    What we would like to do is pass a pair of values /inward/ rather
    than /outward/, and have a function that returns a single value
    using tail recursion: This approach can be programmed as:

    typedef unsigned long long Number;

    unsigned high_bit_mask( unsigned m, unsigned n );
    Number ff2( Number a, Number b, unsigned high_ones, unsigned n );

    Number
    fast_fibonacci( unsigned n ){
    return ff2( 1, 0, high_bit_mask( -1, n ), n );
    }

    unsigned
    high_bit_mask( unsigned m, unsigned n ){
    return (m & n) == 0 ? ~m ^ ~m>>1 : high_bit_mask( m<<1, n );
    }

    Number
    ff2( Number a, Number b, unsigned m, unsigned n ){
    return m == 0 ? b
    : m & n ? ff2( 2*a*b + b*b, a*a + 2*a*b + 2*b*b, m>>1, n )
    : ff2( a*a + b*b, 2*a*b + b*b, m>>1, n );
    }

    As a side benefit this illustrates a technique for turning a
    "high-to-low" recursion using even-/odd-ness into a form that
    is nicely tail recursive. (Notice how the bit mask 'm' picks
    off the bits of 'n' from top to bottom.)

    Incidentally, the optimized generated code for this formulation
    has a property I didn't expect, namely, the main loop in ff2()
    is compiled as a single path with only one conditional branch
    in it (and in particular not two). The compiler (gcc something
    on x86-64) was smart enough to notice the common subexpressions
    between the two recursive calls, and tricks out the parameter
    passing using conditional move instructions.

    For anyone interested: which program line arguably ought to
    have a comment, and what comment would be appropriate?
     
    Tim Rentsch, Sep 22, 2013
    #48
  9. gdotone

    Ike Naar Guest

    For me it's the line above (see below)
     
    Ike Naar, Sep 24, 2013
    #49
  10. gdotone

    Tim Rentsch Guest

    Hmm. Suppose you saw the function defined using an
    iterative form rather than a recursive form, eg,

    unsigned
    high_bit_mask( unsigned n ){
    unsigned m = -1;
    while( m & n ) m <<= 1;
    return ~m ^ ~m>>1;
    }

    would you have the same reaction?
     
    Tim Rentsch, Sep 25, 2013
    #50
  11. gdotone

    Ike Naar Guest

    Nevermind. The bit trickery seemed a bit intimidating at first,
    but a closer look revealed that it simply computes the largest
    power of 2 that is <= n.
     
    Ike Naar, Sep 26, 2013
    #51
    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.