….

A Simple Algorithm: Fibonacci Numbers

One of the simplest and most famous algorithms in computer science is the Fibonacci sequence. It’s an excellent way to understand how algorithms work and how they can be written in different styles.

The Fibonacci sequence is named after Leonardo of Pisa (known as Fibonacci), a 13th-century Italian mathematician.

The sequence starts with 0 and 1. Every next number is the sum of the two preceding numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

This pattern makes Fibonacci numbers a perfect example for practicing loops, recursion, and mathematical formulas.

---

The Fibonacci Algorithm – How It Works

The logic is simple:

1. Start with two numbers: 0 and 1.
2. Add them to get the next number.
3. Shift the pair forward and repeat the process.
4. Continue until you generate as many numbers as you want.

---

Loops vs Recursion

In programming, an algorithm can often be expressed in different ways.
Let’s compare loop-based and recursive solutions for generating Fibonacci numbers.

---

1. Fibonacci Using a Loop

This version uses iteration to generate the first n Fibonacci numbers.

prev2 = 0
prev1 = 1

print(prev2)
print(prev1)

for i in range(18):
    newFibo = prev1 + prev2
    print(newFibo)
    prev2, prev1 = prev1, newFibo

🔹 Fast and efficient — works great for larger sequences.

---

2. Fibonacci Using Recursion

Recursion is when a function calls itself. It’s elegant but less efficient for Fibonacci.

print(0)
print(1)
count = 2

def fibonacci(prev1, prev2):
    global count
    if count <= 19:
        newFibo = prev1 + prev2
        print(newFibo)
        count += 1
        fibonacci(prev1=newFibo, prev2=prev1)

fibonacci(1, 0)

🔹 Simple to understand, but repeated calls make it slower for large numbers.

---

3. Finding the nth Fibonacci Number

We can also use the mathematical definition:

F(n) = F(n-1) + F(n-2)

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

print(F(19))   # Finds the 20th Fibonacci number

🔹 Shows recursion beautifully, but not memory-efficient.

Recursive Fibonacci – The Hidden Cost

When we use recursion for Fibonacci, notice that the function calls itself twice, not just once.
This small detail makes a huge impact on how the program runs.

• Every time we increase the Fibonacci index (n), the number of recursive calls almost doubles.
• This leads to an explosion of calculations as n grows larger.

---

Example: Function Calls for F(5)

If we try to compute F(5), the recursion will expand into many repeated calls:

• F(5) calls F(4) and F(3)
• F(4) further calls F(3) and F(2)
• F(3) calls F(2) and F(1)

And so on, until the base cases F(1) and F(0) are reached.

---

What Happens?

1. Excessive Calls: Many function calls are repeated with the same arguments.
   • Example: F(3) is computed multiple times unnecessarily.
2. Exponential Growth: The number of calls grows roughly like 2^n.
   • For F(5), it’s manageable.
   • For F(50), it becomes millions of calls!

---

Visual Breakdown

1. Function Call Tree
   Shows how the recursive calls expand into a tree with repeated branches.
2. Return Value Flow
   Demonstrates how the values bubble back up, eventually giving the correct result.

---

Key Takeaways

• Recursion is elegant but inefficient for Fibonacci.
• Loops or optimized methods (like memoization or dynamic programming) are much faster.
• The Fibonacci example teaches us why algorithm efficiency matters in real programming.

---

🚀 Keep learning step by step with GoNimbus and strengthen your foundations in DSA!

---