Fibonacci

In 1202, Fibonacci published his sequence. The Fibonacci sequence helped with bookkeeping and charging interest on loans.

Algorithms

We can compute this sequence iteratively, with no recursion. To display a list of Fibonacci numbers, we can make just one iteration through them.

First program

To compute the Fibonacci sequence, we must sum the previous two numbers. This value becomes the next number for the sequence.

def fibonacci(n):
    a = 0
    b = 1
    for i in range(0, n):
        temp = a
        a = b
        b = temp + b
    return a

# Display the first 15 Fibonacci numbers.
for c in range(0, 15):
    print(fibonacci(c))
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377

Display

This method displays Fibonacci numbers as it goes along. For creating a list of Fibonacci numbers, this approach is faster. Just change the "print" statement to a list append call.

def fibonacci2(n):
    a = 0
    b = 1
    for i in range(0, n):
        # Display the current Fibonacci number.
        print(a)

        temp = a
        a = b
        b = temp + b
    return a

# Directly display the numbers.
fibonacci2(15)
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377

A summary

Fibonacci sequences are often used to predict financial markets. Whether anyone can predict financial markets reliably is debatable.

The sequence itself, though, is simple and easy to iteratively compute. Recursion is not necessary. Using a cache (like a list) of numbers would be worthwhile for performance.