Ndtyjky

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)) * (1 + (5 ** 0.5))) ** n) - (((1 / (5 ** 0.5)) * (1 - (5 ** 0.5))) ** n))

else:

    return(recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2))

To display it I am using this:

nterms = 10



if nterms <= 0:

    print("Please Enter a positive integer")

else:

    print("Recursive Fibonacci Sequence: " ,

        [recursive_fibonacci(i) for i in range(nterms)])

    print("Iterative Fibonacci Sequence: " ,

        [iterative_fib(i) for i in range(nterms)])

How would I use an iterative function with this Fibonacci?

I've tried using this:

def iterative_fib(n):

    equation = lambda n: int((((1 / (5 ** 0.5)) * (1 + (5 ** 0.5))) ** n) - (((1 / (5 ** 0.5)) * (1 - (5 ** 0.5))) ** n))

    if n <= 1:

        return equation(n)

    else:

        a, b = 1, 2

        for i in range(n):

            fn = equation((i-a)+(i-b))

        return fn

However this iterative function doesn't seem to have the same output as the recursive function.

The output of the recursive function:

Recursive Fibonacci Sequence:  [0, 2, 2, 4, 6, 10, 16, 26, 42, 68]

The output of the iterative function:

Iterative Fibonacci Sequence:  [0, 2, 2, 2, 3, 6, 13, 27, 58, 122]

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.

def fib(N):

    return int((g**N - (1-g)**N) / 5**.5)

Contrast with,

def fib_iterative(N):

    a, b, i = 0, 1, 2

    yield from (a, b)

    while i < N:

        a, b = b, a + b 

        yield b

        i += 1

And we have

>>> [fib(n) for n in range(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]

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 -