please discuss recursive calls, program provided.

[Ben Bacarisse]

Here's one that should be more efficient for large n,
it computes Fib(n) in logarithmic time:

typedef unsigned long long num;

static num fib_aux(int n, num p, num q, num r, num x, num y)
{
if (n == 0)
{
return x;
}
else if (n % 2 == 0)
{
return fib_aux(n/2, p*p+q*q, (p+r)*q, q*q+r*r, x, y);
}
else
{
return fib_aux(n-1, p, q, r, p*x+q*y, q*x+r*y);
}
}

num fib(int n)
{
return fib_aux(n, 0, 1, 1, 0, 1);
}

It's based on the observation that (in matrix notation)

[ Fib(n) ] [ p q ] [ 0 ]
[ Fib(n+1) ] = [ q r ] * [ 1 ]

where
n
[ p q ] [ 0 1 ]
[ q r ] = [ 1 1 ]

I didn't know that one. Thanks.

<snip>

 

[Joe Pfeiffer]

A little off-topic (I'm interested in the floodfill, not so
much recursion, per se), but would the scaleable floodfill
work for something like...
. .
|\ /|
| \ / |
| \ / |
| \ / ? |
| x \ /left|
| \/blank|
| |
| |
+------------+
If you start at point x (any point in the upper left-hand-side
triangle), won't the entire region of the upper right-hand-side
triangle be missed? Thanks,

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

 

[Malcolm McLean]

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

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.

 

[Seebs]

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.

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

-s

 

[blmblm]

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

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?

 

[Seebs]

What does "this" mean, in context ....
Recursion.

I'm not thinking off the top of my
head how recursion would otherwise be useful for reading all lines ....

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

 

[blmblm]

Recursion.

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

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();
}

"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?"

 

[Tim Rentsch]

OK:

typedef unsigned long long number;

static number fib_aux(number a, number b, int n)
{
if (n <= 1) return a;
else return fib_aux(b, a+b, n-1);
}

number rfib(int n) { return fib_aux(1, 1, n); }

Very nice, a recursive solution that computes Fib(n) in linear time.

Here's one that should be more efficient for large n,
it computes Fib(n) in logarithmic time: [snip program]

It's based on the observation that (in matrix notation)

[ Fib(n) ] [ p q ] [ 0 ]
[ Fib(n+1) ] = [ q r ] * [ 1 ]

where
n
[ p q ] [ 0 1 ]
[ q r ] = [ 1 1 ]

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?

 

[Ike Naar]

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

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

 

[Tim Rentsch]

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

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?

 

[Ike Naar]

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?

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.