Learn Fibonacci Series: Loop, Recursion, and Dynamic Programming

by

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. So, the series goes:

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

Each number in the Fibonacci sequence (starting from the third number) can be represented by the formula:

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

where:

  • F(0)=0
  • F(1)=1

Fibonacci Series Code in Python

Here’s a simple code in Python to generate Fibonacci numbers.

Method 1: Using a Loop
def fibonacci(n):
    a, b = 0, 1
    fibonacci_sequence = []
    
    for _ in range(n):
        fibonacci_sequence.append(a)
        a, b = b, a + b  # Update a and b to the next numbers in the sequence
    
    return fibonacci_sequence

Explanation:

  • We initialize the first two numbers, a = 0 and b = 1.
  • For each iteration, we add a to the Fibonacci sequence list, then update a and b to the next two numbers.
  • This loop continues until we have generated n numbers in the sequence.
Example Usage
print(fibonacci(10))  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Method 2: Using Recursion

A recursive function can also generate Fibonacci numbers. However, recursion is less efficient for larger values of n.

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

# Generate a list of Fibonacci numbers
fibonacci_sequence = [fibonacci_recursive(i) for i in range(10)]
print(fibonacci_sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Explanation:
  • fibonacci_recursive calls itself twice to calculate F(n-1) and F(n-2).
  • This continues until the base case, n <= 1, where it simply returns n.
  • This method is easy to understand but slow for large n due to repeated calculations.

Method 3: Using Dynamic Programming (Efficient)

To avoid redundant calculations in recursion, we can use dynamic programming with memorization.

def fibonacci_dynamic(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_dynamic(n-1, memo) + fibonacci_dynamic(n-2, memo)
    return memo[n]

# Generate a list of Fibonacci numbers
fibonacci_sequence = [fibonacci_dynamic(i) for i in range(10)]
print(fibonacci_sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Explanation:
  • memo is a dictionary that stores previously computed values of Fibonacci numbers.
  • This avoids recomputation and significantly speeds up the calculation for larger values of n.

Description

The Fibonacci series is widely used in algorithms, mathematics, and computer science. It often appears in nature, and it’s used as a teaching example for recursion, dynamic programming, and efficient algorithm design.

In practice:

  • Loop method is efficient and easy for small to moderate values.
  • Recursion is simple to understand but inefficient for large values.
  • Dynamic Programming (Memoization) is highly efficient, especially for large values of n.

These methods provide a foundation for understanding not only the Fibonacci series but also the principles of recursion, optimization, and performance improvement in algorithm design.

Leave a Comment