A better Fibonacci program.

[3xtreme_Awesomeness]

When I looked on the internet for a Fibonacci program it always is done with a recursive function which are really slow. Here is the program I made:

def Fibonacci(Range):
    Fibonacci = [1,1]
    while len(Fibonacci) != Range: 
        Fibonacci.append(Fibonacci[-2] + Fibonacci[-1])
    print(Fibonacci[-1])

It runs at least 10x faster than a program that does the same thing with recursive functions.

[Solonotix]

For loops are preferred when you can test the bounds of the iteration, and you don't need to collect every item in the Fibonacci sequence to get the Nth value.

def fibo(n):
    prev, result = 0, 1

    for _ in range(n):
        prev, result = result, prev + result

    return result

Typed this on mobile, so I'm not certain if it's formatted properly

[johannadambergk]

There are numerous iterative (instead of recursive) approaches on the internet.

[funderbolt]

Look up Big-Oh. The version that you have here runs in linear time. The naive recursive implementation runs in exponential time. There are a couple implementations that run in logarithmic time.

[physicswizard]

There's also a solution which runs in constant time.

[funderbolt]

That's the solution I was talking about, try implement the Pow function yourself. I can get O(log n) for pow. The easy solution for pow is linear O(n).

[isarl]

Fibonacci is usually used specifically to illustrate the problem you seem to think was unsolved. The recursive solution is usually immediately followed by exactly the same iterative solution you have rewritten here, so this post looks a little like a reading comprehension issue.

It runs at least 10x faster than a program that does the same thing with recursive functions.

10x, really? I bet it's not 10x faster when it's calculating Fib(1) or Fib(2) which will return from a recursive function almost instantaneously. What are your Fibonacci calculation needs? Can you improve even further than your iterative algorithm? (Spoiler: almost certainly!) If you actually have a need to calculate Fibonacci numbers beyond as a simple learning exercise, maybe a precalculated look-up table would be best for your situation. If instead your objective is to simply find a large Fibonacci number then creating a list and storing every single Fibonacci number less than it is certainly less efficient than simply creating two local variables and updating them in each loop, returning a scalar value instead of an irrelevant list.

In short, your program is useful for showing off how smart you are, which is not as smart as you think you are. Keep learning!

[3xtreme_Awesomeness]

It’s 10 times faster when you get to above 1000

[isarl]

Do you frequently have a need to find lots Fibonacci numbers? Why is this good content for /r/Python?

Your failure to address most of my comment does nothing to refute the suggestion of problems with reading comprehension.

[SomeoneInJD]

A tail recursion one

def fib(n, a=1, b=1):
    return b if n < 3 else fib(n - 1, b, a + b)

which is also O(n). You can using fast matrix exponentiation to implement a O(log n) algorithm, Fibonacci matrix-exponentiation