Matthew Hannigan wrote:
<snipped>
I was going to mention it as part of saying that the usual
fibonacci example of recursion is a spectacularly bad
example for recursion (without tail recursion elimination)
Perhaps, it will help understand if I supply the following description
and C codes of fibonacci numbers:
/* fibonacci number defined as sum of two
previous fibonacci numbers,i.e.,
f(n) = f(n-2) + f(n-1), where n > 1, and
Let, by definition:
f(0) = 0
f(1) = 1
e.g.
#./fib 10
55
*/
#include <stdio.h>
#include <stdlib.h>
typedef unsigned u__;
u__ fibc( u__ n, u__ x, u__ y ){
return n == 0 ? y : fibc( n-1, y, x+y );
}
u__ fib( u__ n ){
return fibc( n, 1, 0 ); /* means return 0, if n =0;
return 1, if n =1;
recurse
fibc(), if n > 1
*/
}
int main(int argc, char *argv[]){
/* Default n value is 2 - calculate fibonacci of 2 */
u__ u, n = 2;
if (argc < 2) u = n;
else u = (u__)atoi(argv[1]);
printf("%8u\n",fib((u__)u));
return (0);
}
Then,
#cc -g fib.c -o fib
#gdb ./fib 10
(gdb)break main
(gdb)r
(gdb)s (at least 10 times)
(gdb)bt
(gdb)q (when done)
because the stack grows exponentially -- there being two
recursive calls for every call.
O Plameras
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
