Fibonacci Series in Python | Code, Algorithm & More

Fibonacci Series in Python | Code, Algorithm & More

Time Stamp: September 14, 2023 3:00 PM
Source Node: 2881385

Introduction

The Fibonacci series in python is a mathematical sequence that starts with 0 and 1, with each subsequent number being the sum of the two preceding ones. In Python, generating the Fibonacci series is not only a classic programming exercise but also a great way to explore recursion and iterative solutions.

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n > 1

Table of contents

What is the Fibonacci Series?

The Fibonacci series is a sequence where every number is the sum of the two numbers preceding it, beginning with 0 and 1. 

Fibonacci Series in Python
Source: TecAdmin

Want to Learn Python for Free? Explore our Free Course Today!

Mathematical Formula for the Fibonacci Sequence

The mathematical formula to calculate the Fibonacci sequence is: 

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

Where:

  • F(n) is the nth Fibonacci number
  • F(n-1) is the (n-1)th Fibonacci number
  • F(n-2) is the (n-2)th Fibonacci number

Recursive Definition

The recursive definition of the Fibonacci series is dependent on the recursive system.

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n > 1

So, every number in the Fibonacci series is calculated by including the two numbers  before it. This recursive method continues generating the entire sequence, starting from  0 and 1.

Also Read: Top 10 Uses of Python in the Real World with Examples

Recursive Fibonacci Series in Python

Fibonacci numbers recursively in Python using recursive features. Here’s a Python code  to calculate the nth Fibonacci number by using recursion:

Def fibonacci(n): if n <= 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci (n-2)
#import csv

Iterative Fibonacci Series in Python,

An iterative method to calculate Fibonacci numbers in Python, involves using loops to build the sequence iteratively. 

Iterative Fibonacci Algorithm in Python:

def fibonacci_iterative(n): if n <= 0: return 0 elif n == 1: return 1 Else: fib_prev = 0 # Initialize the first Fibonacci number fib_current = 1 # Initialize the second Fibonacci number For _ in range(2, n + 1): fib_next = fib_prev + fib_current # Calculate the next Fibonacci number fib_prev, fib_current = fib_current, fib_next # Update values for the next iteration return fib_current
#import csv

Comparison with the Recursive Approach

Distinction basis Recursive Approach Iterative Approach
Efficiency This approach is more efficient for large “n” values, calculating the Fibonacci numbers iteratively and without redundant calculations. This approach is less efficient, especially for large “n” as it causes redundant calculations.
Time Complexity 0(n) (Linear) 0 (2^n) (Exponential) 
Space Complexity 0(1) (Constant)  0(n) (Linear) 

Memoization for Efficient Calculation

Memoization is a method that speeds computer programs or algorithms by storing the results of expensive function calls and returning the cached result when the same inputs occur again. It is useful in optimizing Fibonacci calculations as the recursive approach recalculates the same Fibonacci numbers many times, leading to inefficiency.

How Memoization Reduces Redundant Calculations

In Fibonacci calculations, without memoization, the recursive algorithm recalculates the same numbers again and again .Memoization fixes this issue by storing the results. When the function is called again with the same input, it uses the calculated result for the problem.

Implementing Memoization in Python for Fibonacci

Here’s how you implement  memoization in Python to optimize Fibonacci calculations:

# Create a dictionary to store computed Fibonacci numbers.
Fib_cache = {}
def fibonacci_memoization(n): if n <= 0: return 0 elif n == 1: return 1 # Check if the result is already within the cache. If n in fib_cache: return fib_cache[n] # If not, calculate it recursively and store it in the cache. fib_value = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2) fib_cache[n] = fib_value return fib_value
#import csv

Dynamic Programming for Python Fibonacci Series

Dynamic programming is a strategy used to solve problems by breaking them down into smaller subproblems and fixing each subproblem only once, storing the results to avoid redundant calculations. This approach is very effective for solving complex problems like calculating Fibonacci numbers successfully.

Explanation of the Dynamic Programming Approach to Fibonacci:

Dynamic programming involves storing Fibonacci numbers in an array or dictionary when they’re calculated so that they can be reused whenever needed. Instead of recalculating the same Fibonacci numbers, dynamic programming stores them once and retrieves them as needed.

The dynamic programming approach can be used with either an array or a dictionary (hash table) to store intermediate Fibonacci numbers. 

def fibonacci_dynamic_programming(n): fib = [0] * (n + 1) # Initialize an array to store Fibonacci numbers. Fib[1] = 1 # Set the base cases. For i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2] # Calculate and store the Fibonacci numbers. Return fib[n] # Return the nth Fibonacci number.
#import csv

Benefits of Dynamic Programming in Terms of Time Complexity

The dynamic programming method for calculating Fibonacci numbers gives several advantages in terms of time complexity:

Reduced Time Complexity: Dynamic programming reduces the time complexity of Fibonacci calculations from exponential (O(2^n)) in the naive recursive approach to linear (O(n)).

Efficient Reuse: By storing intermediate results, dynamic programming avoids redundant calculations. Each Fibonacci number is calculated once and then retrieved from memory as and when needed, enhancing efficiency.

Improved Scalability: The dynamic programming method remains efficient even for big values of “n,” making it appropriate for practical applications.

Space Optimization for Fibonacci

Space optimization strategies for calculating Fibonacci numbers aim to reduce memory utilization by storing only the important previous values rather than the entire sequence. These techniques are especially useful when memory efficiency is a concern.

Using Variables to Store Only Necessary Previous Values

One of the most regularly used space-optimized strategies for Fibonacci is to apply variables to store only the two most recent Fibonacci numbers rather than an array to store the complete sequence. 

def fibonacci_space_optimized(n): if n <= 0: return 0 elif n == 1: return 1 fib_prev = 0 # Initialize the preceding Fibonacci number. Fib_current = 1 # Initialize the current Fibonacci number. For _ in variety(2, n + 1): fib_next = fib_prev + fib_current #Calculate the next Fibonacci number. fib_prev, fib_current = fib_current, fib_next # Update values for the next iteration. Return fib_current # Return the nth Fibonacci number. #import csv

Trade-offs Between Space and Time Complexity

Space-optimized techniques for Fibonacci come with trade-offs among space and time complexity:

Space Efficiency: Space-optimized approaches use much less memory because they store only a few variables (generally two) to keep track of the latest Fibonacci numbers. This is relatively space-efficient, making it suitable for memory-constrained environments.

Time Efficiency: While these strategies are not linear (O(n)) in terms of time complexity, they may be slightly slower than dynamic programming with an array because of the variable assignments. However, the difference is normally negligible for practical values of “n”.

Generating Fibonacci Numbers up to N

Generating Fibonacci numbers up to N Python can be done with a loop. Here’s a Python code  that generates Fibonacci numbers up to N:

def generate_fibonacci(restriction): if limit <= 0: return [] fibonacci_sequence = [0, 1] # Initialize with the first two Fibonacci numbers. While True: next_fib = fibonacci_sequence[-1] + fibonacci_sequence[-2] if next_fib > restriction: break fibonacci_sequence.append(next_fib) return fibonacci_sequence
#import csv

Applications of Generating Fibonacci Sequences within a Range

  • Number Series Analysis: Generating Fibonacci numbers within a limit can be useful for analyzing and studying number sequences, identifying patterns, and exploring mathematical properties.
  • Performance Analysis: In computer science and algorithm evaluation, Fibonacci sequences can be used to analyze the performance of algorithms and data structure, mainly in terms of time and space complexity.
  • Application Testing: In application testing, Fibonacci numbers may be used to create test cases with varying input sizes to assess the performance and robustness of software applications.
  • Financial Modeling: Fibonacci sequences have applications in financial modeling, specifically in studying market trends and price movements in fields like stock trading and investment analysis.

Fibonacci Series Applications

The Fibonacci sequence has many real-world applications. In nature, it describes the arrangement of leaves, petals, and seeds in plants, exemplifying efficient packing. The Golden Ratio derived from Fibonacci proportions is used to create aesthetically desirable compositions and designs. In technology, Fibonacci numbers play a role in algorithm optimization, such as dynamic programming and memoization, enhancing performance in responsibilities like calculating massive Fibonacci values or solving optimization problems. Moreover, Fibonacci sequences are utilized in financial modeling, assisting in market analysis and predicting price trends. These real-world applications underscore the significance of the Fibonacci series in mathematics, nature, art, and problem-solving.

Fibonacci Golden Ratio

The Fibonacci Golden Ratio, often denoted as Phi (Φ), is an irrational range approximately equal to 1.61803398875. This mathematical constant is deeply intertwined with the Fibonacci sequence. As you progress in the Fibonacci sequence, the ratio among consecutive Fibonacci increasingly approximates Phi. This connection gives rise to aesthetic principles in design, where elements are often proportioned to Phi, creating visually harmonious compositions. Practical examples include the architecture of the Parthenon, artwork like the Mona Lisa, and the proportions of the human face, highlighting the Golden Ratio’s extensive use in achieving aesthetically fascinating and balanced designs in numerous fields, from art and architecture to graphic and web design.

Fibonacci in Trading and Finance

Fibonacci plays a crucial role in trading and finance through Fibonacci retracement and extension levels in technical analysis. Traders use these levels to identify potential support and resistance points in financial markets. The Fibonacci series helps in predicting stock market trends by identifying key price levels where reversals or extensions are likely. Fibonacci trading techniques involve using these levels in conjunction with technical indicators to make knowledgeable trading decisions. Traders regularly look for Fibonacci patterns,  like the Golden Ratio, to help assume price movements. 

Conclusion

While seemingly rooted in mathematics, the Fibonacci series also has relevance in data science. Understanding the principles of sequence generation and pattern recognition inherent in the Fibonacci series can aid data scientists in recognizing and analyzing recurring patterns within datasets, a fundamental aspect of data analysis and predictive modeling in data science.. Enroll in our free Python course to advance your python skills.

Frequently Asked Questions

Q1. What is the Fibonacci series?

A. The Fibonacci series is a sequence of numbers that starts with 0 and 1, in which every next number is the sum of the two previous ones

Q2. What is the formula of the Fibonacci Series?

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

Q3. What is the Fibonacci series of 5?

A. The Fibonacci series up to the 5th number is: 0, 1, 1, 2, 3. So, the Fibonacci number is 3.

Q4. What are the first 20 Fibonacci series

A. The first 20 Fibonacci series are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, and 4181.

Time Stamp:

More from Analytics Vidhya