Fibonacci Sequence

Sequence

Fibonacci sequence is a sequence where each subsequent number is the sum of the previous two. [1]

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Math

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

or

Python

Loop

def fib(count):
    a = 0
    b = 1
    print b
    for i in range(count):
        c = a + b
        print c
        a = b
        b = c

fib(100)

Recursion

Recursion:

def fib(count, last=0, current=1):
    if count < 1: return
    print current
    fib(count-1, current, last+current)

fib(100)

---

WARNING: It appears the recursion will fail after about 999 recursive calls with:

RuntimeError: maximum recursion depth exceeded

Tested with (until it blew up):

def fib(count=1, last=0, current=1):
  print count
  fib(count+1, current, last+current)

fib()