please discuss recursive calls, program provided.

[Ben Bacarisse]

I would be very surprised to see a recursive Fibonacci that is both
anywhere near as efficient as the obvious iterative solution

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

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
number t = a;
a = b;
b = t + b;
}
return a;
}

Compiled separately (to prevent in-lining) from a driver:

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

typedef unsigned long long number;

number rfib(int);
number ifib(int);

int main(int argc, char **argv)
{
int n = argc > 1 ? atoi(argv[1]) : 10;
number sdiff = 0;
for (int i = 1; i <= n; i++)
sdiff += rfib(i) - ifib(i);
printf("%lld\n", sdiff);
return 0;
}

Here is the gprof output from running this program with argv[1] 100000
(even with unsigned long long, you are not actually getting the right
numbers, but it's hard to test otherwise).

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
52.69 3.40 3.40 100000 34.04 34.04 ifib
48.32 6.53 3.12 100000 31.21 31.21 rfib

I will admit to picking the best of three to make a point, but in all
cases ifib and rfib were timed at essentially the same speed -- which
comes out faster is in statistical noise. (Compiled with -O2, though it
may depend on compiler version.)

and even
remotely near as clear as either the obvious iterative solution or the
obvious recursive solution.

I think the recursive function makes the rule that defines the sequence
much clearer than the loop does, but I accept that that may be a matter
of opinion. That aside, I don't think you can say that it's not
"remotely near as clear" as the alternatives.

 

[Ben Bacarisse]

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

For example, functions in functional programming languages are often
written recursively for lists. The most natural way to write a "list
length" function in Haskell is:

length :: [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs

.... and my favourite Haskell Fibonacci sequence

fib = 1 : 1 : map zipWith (+) fib (tail fib)

which is, I think, due to David Turner. You get an unbounded list to do
with as you please.

<snip>

 

[Öö Tiib]

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.

For example painting a complex region that should be same-colored.
Humans do it quite similarly to flood fill algorithm. It is hard to
imagine non-recursive and efficient flood fill algorithm. For other
example searching something from building methodically by opening
rooms, cabinets in rooms, drawers in cabinets, boxes in drawers and
closing the opened in reverse order.

I agree that the Ackermann function is a good step for serious students of
recursion (but my interest is not that great).

Things like that Ackermann function make recursion to sound like a tool
for rather unusual problems.

 

[Phil Carmody]

I would be very surprised to see a recursive Fibonacci that is both
anywhere near as efficient as the obvious iterative solution

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

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
number t = a;
a = b;
b = t + b;
}
return a;
}

Compiled separately (to prevent in-lining) from a driver:

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

typedef unsigned long long number;

number rfib(int);
number ifib(int);

int main(int argc, char **argv)
{
int n = argc > 1 ? atoi(argv[1]) : 10;
number sdiff = 0;
for (int i = 1; i <= n; i++)
sdiff += rfib(i) - ifib(i);
printf("%lld\n", sdiff);
return 0;
}

Here is the gprof output from running this program with argv[1] 100000
(even with unsigned long long, you are not actually getting the right
numbers, but it's hard to test otherwise).

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
52.69 3.40 3.40 100000 34.04 34.04 ifib
48.32 6.53 3.12 100000 31.21 31.21 rfib

I will admit to picking the best of three to make a point, but in all
cases ifib and rfib were timed at essentially the same speed -- which
comes out faster is in statistical noise. (Compiled with -O2, though it
may depend on compiler version.)

Looking at the code, the first thing that went through my mind was
"they should compile to essentially the same thing".

I don't know what they do on your platform, but GCC on POWER supports
that rather well:

00000000 <rfib>:
typedef unsigned long long number;

static number fib_aux(number a, number b, int n)
{
if (n <= 1) return a;
0: 2f 83 00 01 cmpwi cr7,r3,1
4: 39 20 00 00 li r9,0
8: 39 40 00 01 li r10,1
c: 40 9d 00 40 ble- cr7,4c <rfib+0x4c>
10: 38 63 ff ff addi r3,r3,-1
14: 39 60 00 00 li r11,0
18: 7c 69 03 a6 mtctr r3
1c: 39 80 00 01 li r12,1
20: 48 00 00 20 b 40 <rfib+0x40>
24: 60 00 00 00 nop
28: 60 00 00 00 nop
2c: 60 00 00 00 nop
30: 7d 4c 53 78 mr r12,r10
34: 7d 2b 4b 78 mr r11,r9
38: 7d 0a 43 78 mr r10,r8
3c: 7c e9 3b 78 mr r9,r7
else return fib_aux(b, a+b, n-1);
40: 7d 0a 60 14 addc r8,r10,r12
44: 7c e9 59 14 adde r7,r9,r11
typedef unsigned long long number;

static number fib_aux(number a, number b, int n)
{
if (n <= 1) return a;
48: 42 00 ff e8 bdnz+ 30 <rfib+0x30>
else return fib_aux(b, a+b, n-1);
}

number rfib(int n) { return fib_aux(1, 1, n); }
4c: 7d 44 53 78 mr r4,r10
50: 7d 23 4b 78 mr r3,r9
54: 4e 80 00 20 blr
58: 60 00 00 00 nop
5c: 60 00 00 00 nop

00000060 <ifib>:

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
60: 2f 83 00 01 cmpwi cr7,r3,1
64: 39 20 00 00 li r9,0
68: 39 40 00 01 li r10,1
6c: 40 9d 00 40 ble- cr7,ac <ifib+0x4c>
70: 38 63 ff ff addi r3,r3,-1
74: 39 60 00 00 li r11,0
78: 7c 69 03 a6 mtctr r3
7c: 39 80 00 01 li r12,1
80: 48 00 00 18 b 98 <ifib+0x38>
84: 60 00 00 00 nop
88: 60 00 00 00 nop
8c: 60 00 00 00 nop
90: 7d 0a 43 78 mr r10,r8
94: 7c e9 3b 78 mr r9,r7
number t = a;
a = b;
b = t + b;
98: 7d 0a 60 14 addc r8,r10,r12
9c: 7c e9 59 14 adde r7,r9,r11
number rfib(int n) { return fib_aux(1, 1, n); }

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
a0: 7d 4c 53 78 mr r12,r10
a4: 7d 2b 4b 78 mr r11,r9
a8: 42 00 ff e8 bdnz+ 90 <ifib+0x30>
number t = a;
a = b;
b = t + b;
}
return a;
}
ac: 7d 44 53 78 mr r4,r10
b0: 7d 23 4b 78 mr r3,r9
b4: 4e 80 00 20 blr


A POWER machine (running debian stable) is far more metronomic
than many other machines, and the lack of statistical noise is
quite interesting:

% cumulative self self total
time seconds seconds calls us/call us/call name
50.24 12.60 12.60 100000 126.00 126.00 ifib
49.76 25.08 12.48 100000 124.80 124.80 rfib

50.28 12.61 12.61 100000 126.10 126.10 ifib
49.72 25.08 12.47 100000 124.70 124.70 rfib

50.22 12.60 12.60 100000 126.00 126.00 rfib
49.78 25.09 12.49 100000 124.90 124.90 ifib

I think the recursive function makes the rule that defines the sequence
much clearer than the loop does, but I accept that that may be a matter
of opinion. That aside, I don't think you can say that it's not
"remotely near as clear" as the alternatives.

Your recursive function would be my method of choice, thanks for going
to the effort of selling tail recursion so effectively.

Phil

 

[Joe Pfeiffer]

I would be very surprised to see a recursive Fibonacci that is both
anywhere near as efficient as the obvious iterative solution

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

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
number t = a;
a = b;
b = t + b;
}
return a;
}

Compiled separately (to prevent in-lining) from a driver:

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

typedef unsigned long long number;

number rfib(int);
number ifib(int);

int main(int argc, char **argv)
{
int n = argc > 1 ? atoi(argv[1]) : 10;
number sdiff = 0;
for (int i = 1; i <= n; i++)
sdiff += rfib(i) - ifib(i);
printf("%lld\n", sdiff);
return 0;
}

Here is the gprof output from running this program with argv[1] 100000
(even with unsigned long long, you are not actually getting the right
numbers, but it's hard to test otherwise).

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
52.69 3.40 3.40 100000 34.04 34.04 ifib
48.32 6.53 3.12 100000 31.21 31.21 rfib

I will admit to picking the best of three to make a point, but in all
cases ifib and rfib were timed at essentially the same speed -- which
comes out faster is in statistical noise. (Compiled with -O2, though it
may depend on compiler version.)

and even
remotely near as clear as either the obvious iterative solution or the
obvious recursive solution.

I think the recursive function makes the rule that defines the sequence
much clearer than the loop does, but I accept that that may be a matter
of opinion. That aside, I don't think you can say that it's not
"remotely near as clear" as the alternatives.

Ummm... you're right, this is certainly in the same ballpark of
efficiency. As for clarity, that must necessarily be a matter of
opinion -- but this doesn't strike me clear at all without a lot of
effort devoted to reading it.

 

[Ben Bacarisse]

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

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
number t = a;
a = b;
b = t + b;
}
return a;
}

[/QUOTE]

Looking at the code, the first thing that went through my mind was
"they should compile to essentially the same thing".

Yes, they are, essentially, the same algorithm. The only slight
difference is that the shuffling of 'a' though a temporary can be
avoided using parameter passing semantics.

I don't know what they do on your platform,

For the record, here's what gcc 4.7.3 makes of it on my laptop. I've
snipped the junk and put the two side-by-side:

rfib: ifib:
..LFB1: .LFB2:
cmpl $1, %edi cmpl $1, %edi
movl $1, %eax leal -1(%rdi), %edx
jle .L4 movl $1, %eax
movl $1, %edx jle .L10
jmp .L3 movl $1, %ecx
..L5: jmp .L9
movq %rcx, %rax .L11:
..L3: movq %rsi, %rax
subl $1, %edi .L9:
leaq (%rdx,%rax), %rcx subl $1, %edx
movq %rax, %rdx leaq (%rcx,%rax), %rsi
cmpl $1, %edi movq %rax, %rcx
jne .L5 jne .L11
rep rep
ret ret
..L4: .L10:
rep rep
ret ret

<snip>

 

[Phil Carmody]

They will be equally clear *after* you home some basic understanding of
recursion. Recursion is, IMO, a pretty unnatural way of doing things.

I'm perfectly prepared to believe I'm in a minority, but few things
are more natural than recursion to me.

I can't think of much in daily life or thought that is analogous to recursion.

A journey of a thousand miles begins with a single step, and continues
with a slightly less long journey that can be similarly addressed.

Phil

 

[Ben Bacarisse]

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

number ifib(int n)
{
number a = 1, b = 1;
while (n-- > 1) {
number t = a;
a = b;
b = t + b;
}
return a;
}

I think the recursive function makes the rule that defines the sequence
much clearer than the loop does, but I accept that that may be a matter
of opinion. That aside, I don't think you can say that it's not
"remotely near as clear" as the alternatives.

Ummm... you're right, this is certainly in the same ballpark of
efficiency.[/QUOTE]

Ballpark?! They're in the same back yard! You really can't separate
them, at least on the couple of architectures that has been posted.

As for clarity, that must necessarily be a matter of
opinion -- but this doesn't strike me clear at all without a lot of
effort devoted to reading it.

I find that odd. rfib_aux is two lines (it would be one with a
conditional expression) and needs a one-line call to set up the initial
values. ifib has the same one-line initialisation, but needs five lines
and has an extra variable whose role is unrelated to the overall purpose
of the loop. My point, though, is not to try to bludgeon you into
saying it's clear, but simply that, since the code so short, any lack of
clarity probably stems from a difference in the way we think about code.
In other words, I don't think you can argue that any lack of clarity is
intrinsic to the code.

 

[Eric Sosman]

I'm perfectly prepared to believe I'm in a minority, but few things
are more natural than recursion to me.


A journey of a thousand miles begins with a single step, and continues
with a slightly less long journey that can be similarly addressed.

In a journey of a thousand miles there's a 95% chance that
you'll miss connections at O'Hare.

 

[James Kuyper]

On 9/10/2013 2:45 PM, Phil Carmody wrote: ....

In a journey of a thousand miles there's a 95% chance that
you'll miss connections at O'Hare.

If my flight goes through Atlanta rather than O'Hare (which is usually
the case), I suppose you could argue that it counts as missing the
connection at O'Hare, but that doesn't seem quite right.

[comp.lang.c content dropping rapidly]

 

[Nitin Tripathi]

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.

Hello,

It is always optimized to use Recursive Functions whenever you have large data to process, Since Recursive function works on stack.
To optimize the processing, you can also use the likely and not likely for if and else block to improve the performance.

Find below link useful to understand the Recursive best explained.
http://programmers.stackexchange.com/questions/25052/in-plain-english-what-is-recursion

Thanks,
Nitin Tripathi

 

[James Kuyper]

On 09/10/2013 03:47 PM, Nitin Tripathi wrote:
....

It is always optimized to use Recursive Functions whenever you have large data to process, Since Recursive function works on stack.

Statements involving absolute terms like "always" should generally be
treated with suspicion: "always" is usually an exaggeration, at best,
and is often outright wrong. This is a prime example.

Let's leave aside the ever-controversial question of whether a stack is
even required for a conforming C implementation.

Are you suggesting that non-recursive functions don't work on the stack?
Most of the functions I've ever written are non-recursive, and most of
them made heavy use of the stack. The few recursive functions I've
written have usually involved dynamically allocated N-ary tree
structures, so the recursion mainly involve the heap, not the stack.

It seems to me that both the structure of the data and the nature of the
processing to be performed are much more important than the size of the
data, in determining whether recursion is a good idea.

 

[Malcolm McLean]

On Tuesday, 10 September 2013 15:26:13 UTC+3, osmium wrote:

For example painting a complex region that should be same-
colored.
Humans do it quite similarly to flood fill algorithm. It is hard
to imagine non-recursive and efficient flood fill algorithm.

Naive floodfill is

if(pixel == target)
{
pixel = value;
floodfill(NORTH)
floodfill(SOUTH);
floodfill(EAST);
floodfill(WEST);
}

that's OK for small images. But on a medium-sized to large image
you'll find it's very slow, and can blow the stack. The problem is
that it doesn't have good characteristics for maintaining a
neat tidal edge, you've got too many calls to filled regions.

A scaleable floodfill fills in a horizontal line, then keeps a queue of pixels above and pixels below.

 

[Öö Tiib]

Naive floodfill is

It is easy to produce inefficient algorithms for anything.

A scaleable floodfill fills in a horizontal line, then keeps a
queue of pixels above and pixels below.

Recursive algorithm does same without queues.

 

[Phil Carmody]

On 09/10/2013 03:47 PM, Nitin Tripathi wrote:
...

Statements involving absolute terms like "always" should generally be
treated with suspicion: "always" is usually an exaggeration, at best,
and is often outright wrong. This is a prime example.

Curiously, I'd have said that if any sweeping generalisation
along those lines were to be made it would have been the
exact opposite way round! I'd much rather operate repeatedly
in a huge object (iteration) than pass it around as a parameter
(recursion).

Phil

 

[JohnF]

Naive floodfill is

if(pixel == target)
{
pixel = value;
floodfill(NORTH)
floodfill(SOUTH);
floodfill(EAST);
floodfill(WEST);
}

that's OK for small images. But on a medium-sized to large image
you'll find it's very slow, and can blow the stack. The problem is
that it doesn't have good characteristics for maintaining a
neat tidal edge, you've got too many calls to filled regions.

A scaleable floodfill fills in a horizontal line,
then keeps a queue of pixels above and pixels below.

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,

 

[Ike Naar]

Fibonacci is horribly inefficient as recursion

Not necessarily.
The straightforward (naive?) recursive solution is horribly
inefficient, but very efficient recursive solutions do exist.

 

[glen herrmannsfeldt]

Not necessarily.
The straightforward (naive?) recursive solution is horribly
inefficient, but very efficient recursive solutions do exist.

But as an example for beginning programmers, you have to expect
the most straightforward.

The usual solution that I have seen in the past is to keep a cache
of previously computed values. Since Fibonacci increases exponentially,
the cache won't be very big, and so can have a static size.
Also, it isn't very obvious to beginners.

-- glen

 

[Ike Naar]

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:

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 ]

Of course the recursive algorithm can be easily transformed
to an iterative version.

 

[Malcolm McLean]

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 patch it to check for stray NORTH pixels
when you extend the scan line.
You can devise complex shapes where the queues become very big. But normally you just need 2 * width queues, so
there's limited memory reallocation.