Closed Form Fibonacci Series

I am using Python to create a Fibonacci using this formula: I have this recursive Fibonacci function: def recursive_fibonacci(n): if n <= 1: return int((((1 / (5 ** 0.5))

Solution 1:

The equation you're trying to implement is the closed form Fibonacci series.

Closed form means that evaluation is a constant time operation.

g = (1 + 5**.5) / 2# Golden ratio.deffib(N):
    returnint((g**N - (1-g)**N) / 5**.5)

Contrast with,

deffib_iterative(N):
    a, b, i = 0, 1, 2yieldfrom (a, b)
    while i < N:
        a, b = b, a + b 
        yield b
        i += 1

And we have

>>>[fib(n) for n inrange(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>>list(fib_iterative(10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Solution 2:

I think you've misunderstood the expression f_n for the Fibonacci sequence that you mention.

Notice that it is not a recurrence relation. It is a function of n, i.e., it provides the value of the n-th term when given an n.

Hence, you really don't have a recursive/iterative solution to generate the entire Fibonnaci sequence here.

Plugging in n as 0, 1, 2, 3.. provides the terms 0, 1, 1, 2, .. of the series.

To illustrate, when n = 3, f_3 is calculated as -