Fibonacci Series in Python

Introduction

The Fibonacci series in Python is an enchanting sequence of numbers with a profound presence in nature, art, and algorithms that has been a point of intrigue for millennia. In this tutorial, we'll not only delve deep into its mathematical foundations but also explore the most efficient techniques to compute it using Python. As we progress, we'll unravel why this series remains pivotal for both novice and expert programmers, as well as its broader significance in the fields of science and design.

Overview

Spanning from the spiral arrangements of leaves to the mesmerizing designs in Renaissance art, the Fibonacci series proves its universality across domains. Its simple principle—each number being the sum of its two predecessors—holds within its layers of complexity. Through this tutorial, we aim to guide you through the intricate process of computing the Fibonacci series in Python, illuminating the nuances and performance considerations along the way.

Printing Fibonacci Numbers Using Native Approach

Here is a program for printing Fibonacci number in Python using the native approach:

Code:

p = 8
n1 = 0
n2 = 1
next_num = n2
count = 1

while count <= p:
print(next_num, end=" ")
count += 1
n1, n2 = n2, next_num
next_num = n1 + n2
print()

Explanation:

1. p = 8: This line initializes the variable p with the value 8. This variable represents the number of terms in the Fibonacci sequence that will be generated.

2. n1 = 0 and n2 = 1: These lines initialize two variables, n1 and n2, with the first two terms of the Fibonacci sequence: 0 and 1, respectively.

3. next_num = n2: This line sets the variable next_num to the value of n2, which is the second term in the sequence.

4. count = 1: This line initializes the variable count to 1. It will be used to keep track of how many terms have been printed so far.

5. The while loop: This loop runs as long as count is less than or equal to p, which means it will generate p terms of the Fibonacci sequence.

6. Inside the loop:

• print(next_num, end=" "): This line prints the value of next_num without moving to a new line. The end=" " argument adds a space after each printed number.
• count += 1: This increments the count variable by 1.
• n1, n2 = n2, next_num: This line updates the values of n1 and n2 to the previous and current values of n2 and next_num, respectively. This effectively shifts the values for the next iteration.
• next_num = n1 + n2: This calculates the next number in the sequence by adding n1 and n2.

7. print(): After the loop completes, this line adds a new line to separate the Fibonacci sequence from any subsequent output.

Example Program for Fibonacci Numbers Using Recursion in Python

Here is a Python program to print fibonacci series using recursion:

Code:

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Get the input from the user
num_terms = int(input("Enter the number of Fibonacci terms you want: "))

# Print Fibonacci sequence
print("Fibonacci sequence:")
for i in range(num_terms):
    print(fibonacci(i))

Explanation:

1. def fibonacci(n): This is a recursive function definition that calculates the n-th term of the Fibonacci sequence. It uses the following logic:

• If n is less than or equal to 0, it returns 0.
• If n is 1, it returns 1.
• Otherwise, it recursively calculates the (n-1)-th and (n-2)-th terms using the same Fibonacci function and sums them up.

2. num_terms = int(input("Enter the number of Fibonacci terms you want: ")): This line prompts the user to enter the number of Fibonacci terms they want to generate and converts the input to an integer stored in the variable num_terms.

3. print("Fibonacci sequence:"): This line just prints a header to indicate that the Fibonacci sequence is being printed.

4. for i in range(num_terms): This loop iterates from 0 up to num_terms - 1. This is used to generate the first num_terms of the Fibonacci sequence.

5. Inside the loop:

print(fibonacci(i)): This line prints the i-th term of the Fibonacci sequence by calling the Fibonacci function with argument i.

The code generates the Fibonacci sequence recursively. However, it's important to note that this approach is inefficient for larger values of n due to repeated calculations. This is because the recursive function recalculates the same terms multiple times. A more efficient approach is to use dynamic programming or an iterative approach.

Fibonacci Sequence Using DP (Dynamic Programming)

Here is a program for a Fibonacci sequence Python using dynamic programming:

Code:

def fibonacci_dp(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    
    fib = [0] * (n + 1)
    fib[1] = 1


    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]

    return fib[n]


# Get the input from the user
num_terms = int(input("Enter the number of Fibonacci terms you want: "))

# Print Fibonacci sequence
print("Fibonacci sequence:")
for i in range(num_terms):
    print(fibonacci_dp(i))

Explanation:

This code snippet defines a function fibonacci_dp(n) that calculates the n-th Fibonacci number using a dynamic programming approach.

1. def fibonacci_dp(n): This is a function definition for calculating the n-th Fibonacci number using dynamic programming.

• If n is less than or equal to 0, it returns 0.
• If n is 1, it returns 1.
• Otherwise, it initializes a list fib to store Fibonacci numbers and sets the first two elements fib[0] and fib[1] to 0 and 1, respectively.
• Then, it iteratively calculates and stores the Fibonacci numbers from fib[2] to fib[n] using the formula fib[i] = fib[i - 1] + fib[i - 2].
• Finally, it returns the n-th Fibonacci number, which is fib[n].

2. num_terms = int(input("Enter the number of Fibonacci terms you want: ")): This line prompts the user to enter the number of Fibonacci terms they want to generate and converts the input to an integer stored in the variable num_terms.

3. print("Fibonacci sequence:"): This line just prints a header to indicate that the Fibonacci sequence is being printed.

4. for i in range(num_terms): This loop iterates from 0 up to num_terms - 1. This is used to generate and print the first num_terms Fibonacci numbers.

5. Inside the loop:

print(fibonacci_dp(i)): This line prints the i-th Fibonacci number by calling the fibonacci_dp function with argument i.

The dynamic programming approach efficiently computes Fibonacci numbers by avoiding redundant calculations by storing previously computed values. This makes it a much better choice for larger values of n compared to the naive recursive approach.

Optimization of Fibonacci sequence

Here is an example of optimizing Python Fibonacci series:

Code:

def fibonacci(k):
x = 0
y = 1
if k < 0:
print("wrong input")
elif k == 0:
return 0
elif k == 1:
return y
else:
for i in range(1, k):
z = x + y
x = y
y = z
return y
print(fibonacci(8))

Explanation:

This code defines a function fibonacci(k) that calculates the k-th Fibonacci number using an iterative approach.

1. def fibonacci(k): This is a function definition for calculating the k-th Fibonacci number using an iterative approach.

• x = 0 and y = 1: These variables represent the first two terms of the Fibonacci sequence.

2. if k < 0: This condition checks if the input k is negative.

• If k is negative, it prints "wrong input" to indicate that the input is invalid.

3. elif k == 0: This condition checks if k is equal to 0.

• If k is 0, it returns 0 since the 0-th Fibonacci number is 0.

4. elif k == 1: This condition checks if k is equal to 1.

• If k is 1, it returns 1 since the 1st Fibonacci number is 1.

5. else: If none of the above conditions are met, this means k is greater than 1, so the loop approach will be used.

• The loop iterates from i = 1 to k - 1, which corresponds to generating the k-th Fibonacci number.
• Inside the loop:
• • z = x + y: This calculates the sum of the last two terms, x and y, which will be the next term in the sequence.
  • x = y: This updates x to be the previous value of y.
  • y = z: This updates y to be the calculated value z.

6. return y: After the loop completes, the value of y will hold the k-th Fibonacci number, so the function returns it.

7. print(fibonacci(8)): This line calls the Fibonacci function with an argument of 8 and prints the result.

The iterative approach calculates the Fibonacci number by iteratively updating the values of x and y while progressing through the sequence. This method is more efficient than the naive recursive approach because it avoids redundant calculations.

Fibonacci Sequence Using Cache

Here is another example of a Fibonacci program in Python using the cache:

Code:

from functools import lru_cache
@lru_cache(None)
def fibonacci(n: int) -> int:
if n < 0:
print("wrong input")
return
elif n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(8))

Explanation:

1. from functools import lru_cache: This line imports the lru_cache decorator from the functools module. lru_cache stands for "Least Recently Used Cache" and is used for memoization, which optimizes function calls by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

2. @lru_cache(None): This line decorates the fibonacci function with the lru_cache decorator. The None argument means that there is no limit to the cache size. The decorator will automatically cache the results of function calls, making subsequent calls with the same input more efficient.

3. def fibonacci(n: int) -> int: This is the definition of the fibonacci function. It takes an integer n as an argument and returns an integer.

4. if n < 0: This condition checks if the input n is negative.

• If n is negative, it prints "wrong input" to indicate that the input is invalid.
• Then, it returns without calculating the Fibonacci number.

5. elif n < 2: This condition checks if n is less than 2.

• If n is 0 or 1, it returns n since the 0-th Fibonacci number is 0 and the 1st Fibonacci number is 1.

6. return fibonacci(n - 1) + fibonacci(n - 2): This is the recursive part of the function.

• If none of the above conditions are met, the function calculates the n-th Fibonacci number by recursively summing the (n-1)-th and (n-2)-th Fibonacci numbers.
• The lru_cache decorator ensures that the results of function calls are cached, so repeated calculations are avoided.

7. print(fibonacci(8)): This line calls the fibonacci function with an argument of 8 and prints the result.

By using the lru_cache decorator, this code optimizes the Fibonacci calculation by avoiding redundant calculations and storing previously computed results. This makes the recursive approach much more efficient, especially for larger values of n.

Fibonacci Sequence Using Backtracking in Python

Code:

def fibonacci(x, memo={}):
if x <= 0:
return 0
elif x == 1:
return 1
elif x in memo:
return memo[x]
else:
memo[x] = fibonacci(x-1) + fibonacci(x-2)
return memo[x]

# Driver Program
print(fibonacci(8))

Explanation:

This code defines a fibonacci function that calculates the x-th Fibonacci number using recursion and memoization.

• The fibonacci function takes an argument x and an optional dictionary memo which stores computed Fibonacci values.
• If x is less than or equal to 0, the function returns 0.
• If x is 1, the function returns 1.
• If x is already present in the memo, the function returns the stored value.
• If x is not in the memo, the function recursively calculates the Fibonacci value using x-1 and x-2 terms, stores it in the memo, and returns the value.
• The code demonstrates the fibonacci function's usage by calculating and printing the 8th Fibonacci number.

Programs to Print the Fibonacci Sequence in Python

Another example of the Fibonacci sequence

Code:

def fibonacci_sequence(n):
    fib_sequence = [0, 1]  
    
    for i in range(2, n):
        next_fib = fib_sequence[i - 1] + fib_sequence[i - 2]
        fib_sequence.append(next_fib)
    
    return fib_sequence

num_terms = int(input("Enter the number of Fibonacci terms you want: "))

print("Fibonacci sequence:")
sequence = fibonacci_sequence(num_terms)
for num in sequence:
    print(num)

By using a while loop

Code:

xterms = int(input("How many terms? "))
x1, x2 = 0, 1
c = 0
if xterms <= 0:
   print("Please enter a positive integer")
elif xterms == 1:
   print("Fibonacci sequence upto",xterms,":")
   print(x1)
else:
   print("Fibonacci sequence:")
   while c < xterms:
       print(x1)
       xth = x1 + x2
       x1 = x2
       x2 = xth
       c += 1

Conclusion

Having now journeyed through the depths of the Fibonacci series and its implementation in Python, we've showcased its rich history and contemporary relevance. Understanding the Fibonacci series isn't just a rite of passage for a programmer, but an exploration of a pattern that has transcended time, existing in realms from the branching of trees to the spiraling galaxies.

As you continue your journey in the world of programming and data structures, consider upGrad's comprehensive courses that serve as beacons for upskilling professionals in the digital age.

FAQs

1. What is Fibonacci Series?

A sequence where each number is the sum of the two preceding numbers, beginning usually with 0 and 1.

2. How is the Fibonacci series formula derived?

It's rooted in the golden ratio and mathematical induction, ensuring efficient computation of any Fibonacci number.

3. Can I compute the Fibonacci series in Python without using recursion?

Absolutely! While recursion is a popular method, you can also compute the Fibonacci series using iterative loops, array manipulation, or even formulas like Binet's. Each approach has its advantages, and the choice often depends on considerations like performance needs and code simplicity.

4. What are the real-world applications of the Fibonacci series?

Its patterns are observed in nature, art, and also have applications in algorithms and financial markets.

5. How does the factorial series differ from the Fibonacci series in Python?

While both represent sequences, their computation diverges. Factorial multiplies numbers successively, while Fibonacci adds them.