Re: Fibonacci implementation


Christian Christmann wrote:
Hi,

I'm looking for a non-recursive implementation of the algorithm to
calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
prefered).

Any hints?

No-one seems to have given a straight-forward reply to this. You can do
it in BASIC as follows:

DIM f(n)

f(0) = 0
f(1) = 1

FOR k = 2 TO n
f(k) = f(k - 1) + f(k - 2)
NEXT k

Which is nice and simple. If you want single, large values however it
might be quicker to calculate them directly, as follows:

FUNCTION fib (k)
r = (1 + SQR(5)) / 2
t = 1 - r
fib = (r ^ k - t ^ k) / (r - t)
END FUNCTION

(where SQR is the square root function, ^ is "to the power of" and the
line "fib = " sets the result of the function.

Incidentally, I thought the only reason for writing a recursive
implementation of Fibonacci numbers was to show how recursive functions
can go horribly wrong if you don't think about them carefully.

Hope that helps.
Paul.

.

Relevant Pages

  • Re: Fibonacci implementation
    ... Christian Christmann wrote: ... I'm looking for a non-recursive implementation of the algorithm to ... Have you tried typing "non-recursive fibonacci" into a search engine? ... I found a page showing how to do it in a C/C++ like language 3rd hit ...
    (comp.programming)
  • Re: Fibonacci implementation
    ... Christian Christmann wrote: ... Any language is OK (C/C++, pseudo code ... Code Codex contains many excellent examples, including Fibonacci in many ...
    (comp.programming)