# please discuss recursive calls, program provided.

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

1. ### Ben BacarisseGuest

I didn't know that one. Thanks.

<snip>

Ben Bacarisse, Sep 12, 2013

2. ### Joe PfeifferGuest

No, because you mark pixels both above and below the current scan line
for filling.

Joe Pfeiffer, Sep 12, 2013

3. ### Malcolm McLeanGuest

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
4. ### SeebsGuest

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

-s

Seebs, Sep 14, 2013
5. ### blmblmGuest

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("%s", contents);
return 0;
}

Not practical in any context I can think of, but entertaining?

blmblm, Sep 15, 2013
6. ### SeebsGuest

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

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
8. ### Tim RentschGuest

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
9. ### Ike NaarGuest

For me it's the line above (see below)

Ike Naar, Sep 24, 2013
10. ### Tim RentschGuest

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

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

would you have the same reaction?

Tim Rentsch, Sep 25, 2013
11. ### Ike NaarGuest

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