CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

Different functions that compute the Fibonacci sequence.

Project: MAT 2540
Views: 120
Visibility: Unlisted (only visible to those who know the link)
Image: ubuntu2004
Tweet
Share
Share
Kernel: SageMath 8.6

Fibonacci Sequence

Below is a recursive function that computes the nnth Fibonacci number, fnf_n. The amount of code we write is small, but this cannot compute fnf_n for large nn quickly.

def fib_recursive(n):
    if n <= 1:
        return n
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)

for i in range(5):
    print(fib_recursive(i))
0 1 1 2 3

Below is a function that computes the nnth Fibonacci number, fnf_n, using dynamic programming. This function is faster because it trades time for space.

def fib_dyn(n):
    L = [0,1]
    if n <= 1:
        return n
    else:
        for i in range(n-1):
            L.append(L[-1] + L[-2])
        return L[-1]

for i in range(30):
    print(fib_recursive(i))
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

Below is a function that computes the nnth Fibonacci number, fnf_n, quickly without using much memory.

def fib_dyn(n):
    a, b= 0, 1
    if n <= 1:
        return n
    else:
        for i in range(n-1):
            a, b = b, a+b
        return b

for i in range(30):
    print(fib_recursive(i))
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229