From: Mike McCarty (jmccarty_at_ssd.usa.alcatel.com)
Date: 2001-02-26 20:30:10
On Mon, 26 Feb 2001, BlackJack/Civitas wrote:
[snip]
> [1] recursive functions call:
>
[snip]
> One popular examples of recursive functions are fibonacci numbers. The
> definition is: Every fibonacci number is the sum of the two previous. With
> fib(0) = 0 and fib(1) = 1.
>
> unsigned long fib(unsigned long n) {
> if (n<2) return n;
> return fib(n-1) + fib(n-2);
> }
This is not a particularly popular example. The ususal is factorial().
However, neither of these is a good example, for a number of reasons.
For one, iteration works just as well. For another, there are so few
representable Fibonacci numbers, that they should be precomputed and
stored in an array.
Consider that the largest argument (you used "n" above) which fits into
these bits is:
Number
Bits Argument
---- --------
8 12
16 23
32 46
A lookup table with 47 entries each 32 bits is not very large, and is
quite fast. A lookup table with 24 entries each 16 bits is even smaller.
Mike
----------------------------------------------------------------------
To unsubscribe from the list send mail to majordomo_at_musoftware.de with
the string "unsubscribe cc65" in the body(!) of the mail.
This archive was generated by hypermail 2.1.3 : 2001-12-14 22:05:39 CET