DEV Community

Cover image for Coding The Fibonacci Sequence In Python
Grant Riordan
Grant Riordan

Posted on

Coding The Fibonacci Sequence In Python

#python #beginners #programming

The Fibonacci sequence is a series of numbers where each number is the sum of the previous two:

0, 1, 1, 2, 3, 5, 8, 13, ...
Enter fullscreen mode Exit fullscreen mode

It’s one of the most famous sequences in math and programming — and it turns up a lot!

What triggered me to write this quick blog was a fun example of the Fibonacci algorithm being used on LeetCode's Climbing Stairs problem.

🪜 The Climbing Stairs Story

Imagine a staircase with n steps.

  • You can climb 1 step at a time.

  • Or jump 2 steps at a time (if possible).

How many different ways can you reach the top?

Step Patterns
For the first few steps:

Step 1 → 1 way

Step 2 → 2 ways

1 + 1
2
Enter fullscreen mode Exit fullscreen mode

Step 3 → 3 ways

1 + 1 + 1
1 + 2
2 + 1
Enter fullscreen mode Exit fullscreen mode

Step 4 → 5 ways

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
Enter fullscreen mode Exit fullscreen mode

Do you see a pattern forming?
1, 2, 3, 5...

This is the Fibonacci sequence shifted by one!

Why Fibonacci Appears Here

To reach step n, your last move is either:

1-step from n-1 (e.g 9 -> 10)

2-step from n-2 (e.g 8 -> 10)

So the number of ways to reach step n is:

  𝑤𝑎𝑦𝑠(𝑛) = 𝑤𝑎𝑦𝑠(𝑛−1) + 𝑤𝑎𝑦𝑠(𝑛−2)
Enter fullscreen mode Exit fullscreen mode

Example:
step 10 = ways to get to step9 + ways to get to step 8

We know this because you can either add a 1 to all the ways you got to step 9, and in doing so gets you to step 10,

or you can add 2 to every way you got step 8, and in doing so will get you to step 10

So by adding step8 ways to step9 ways, you get all combinations to step 10.

That is exactly the Fibonacci rule!

Coding the Fibonacci Sequence in Python

Once we see the pattern, we can code Fibonacci directly.

Here’s a simple function that generates the first n Fibonacci numbers:

def fibonacci(n: int) -> list[int]:
    if n <= 0:
        return []

    # Start with the first two Fibonacci numbers
    result = [0, 1]

    # Build the sequence up to n
    for i in range(2, n):
        result.append(result[i - 1] + result[i - 2])

    return result[:n]

# Example: first 13 Fibonacci numbers
print(fibonacci(13))
Enter fullscreen mode Exit fullscreen mode

Outputs:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

Key Takeaways

Fibonacci is everywhere in problems about counting sequences of choices, incremental combinations and more.

The rule is simple:
F(n) = F(n-1) + F(n-2)

Problems like Climbing Stairs are a fun way to discover Fibonacci naturally, if you're learning Python I'd recommend checking out some online coding challenges.

Top comments (0)