Python Program for n-th Fibonacci number

Python Program for n-th Fibonacci number

In this tutorial, we will explore how to compute the nth Fibonacci number using Python. Each number in the series of Fibonacci numbers is equal to the sum of the two numbers that came before it. Starting with 0 and 1, the sequence begins.

For example,

• 0 and 1 are the first two words.
• The formula for the third term is 0+1=10 + 1 = 1.
• 1+1=21 + 1 = 2 is the fourth phrase, and so forth.

The recurrence relation is used to mathematically define this sequence: F(n)=F(n−1)+F(n−2)+ F(n-1) + F(n-2) = F(n)

There are multiple ways to find the nth Fibonacci number in Python, including:

1. Using Recursion
2. Using Dynamic Programming
3. Using Dynamic Programming with Space Optimization
4. Using Arrays

In this article, we’ll focus on the most fundamental approaches and understand them with examples.

Download New Real Time Projects :-Click here

1. Finding nth Fibonacci Number Using Recursion

Recursion refers to a function calling itself until a specific condition is met. It’s a straightforward yet powerful approach for solving problems like finding Fibonacci numbers.

Example:

# Function to calculate the nth Fibonacci number
def Fibonacci_Series(n):
    if n < 0:
        print("Invalid input! Fibonacci numbers are only defined for non-negative integers.")
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci_Series(n - 1) + Fibonacci_Series(n - 2)

# Testing the function
print("12th Fibonacci Number:", Fibonacci_Series(12))

Output:

12th Fibonacci Number: 144

Explanation:

• The function Fibonacci_Series(n) recursively calculates Fibonacci numbers.
• Base cases: It gives 0 if n=0n = 0 and 1 if n=1n = 1.
• Until it reaches the base cases, the function calculates F(n−1)+F(n−2)F(n-1) + F(n-2) for n>1n > 1.

While recursion is intuitive, it can be inefficient for larger values of nn due to repeated calculations.

2. Finding nth Fibonacci Number Using Dynamic Programming

Dynamic Programming avoids repeated calculations by storing intermediate results. This makes the approach efficient.

Example:

# Dynamic programming function to determine the nth Fibonacci number
def Fibonacci_series(n):
    fib_array = [0, 1]  # Initializing the first two Fibonacci numbers

    for i in range(2, n + 1):
        fib_array.append(fib_array[i - 1] + fib_array[i - 2])

    return fib_array[n]

# Testing the function
print("12th Fibonacci Number:", Fibonacci_series(12))

Output:

12th Fibonacci Number: 144

Explanation:

• A list fib_array stores Fibonacci numbers as they are computed.
• The for-loop iterates from index 2 to nn, adding the two preceding values and appending the result to the list.
• Finally, the nth Fibonacci number is returned.

3. Dynamic Programming with Space Optimization

In this method, we further optimize space usage by only keeping the last two computed Fibonacci numbers instead of storing the entire sequence.

Example:

# Function to calculate the nth Fibonacci number with space optimization
def Fibonacci_series(n):
    if n < 0:
        print("Invalid input!")
    elif n == 0:
        return 0
    elif n == 1:
        return 1

    # Initialize the first two numbers
    prev1, prev2 = 0, 1

    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev1, prev2 = prev2, current  # Update the last two numbers

    return prev2

# Testing the function
print("12th Fibonacci Number:", Fibonacci_series(12))

Output:

12th Fibonacci Number: 144

Explanation:

• We only use two variables (prev1 and prev2) to track the last two Fibonacci numbers.
• The for-loop iteratively calculates the next number while updating the variables.
• This approach is both time and space-efficient.

4. Finding nth Fibonacci Number Using Arrays

In this method, an array is explicitly created to store all Fibonacci numbers up to the nth term.

Example:

# Function to calculate the nth Fibonacci number using an array
def Fibonacci_series(n):
    # Create an array to store Fibonacci numbers
    fib_array = [0] * (n + 1)
    fib_array[1] = 1

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

    return fib_array[n]

# Testing the function
print("12th Fibonacci Number:", Fibonacci_series(12))

Output:

12th Fibonacci Number: 144

Explanation:

• The array fib_array is initialized to store n+1n + 1 elements.
• Starting with 0 and 1, the loop fills in the rest of the array by summing the preceding two elements.
• Finally, the nth Fibonacci number is returned.

Conclusion

In this tutorial, we explored various methods to calculate the nth Fibonacci number using Python. Each method has its own advantages:

• Recursion: Simple but inefficient for large inputs.
• Dynamic Programming: More efficient by avoiding redundant calculations.
• Space Optimization: Reduces memory usage.
• Arrays: Useful for scenarios where the entire sequence is needed.

Choose the approach that best suits your requirements!

PHP PROJECT:- CLICK HERE

INTERVIEW QUESTION:-CLICK HERE

Complete Advance AI topics:- CLICK HERE

Complete Python Course with Advance topics:- CLICK HERE

fibonacci series program in python using for loop
fibonacci series in python
python program for n-th fibonacci number
Python Program for n-th Fibonacci number
python program for how to check if a given number is fibonacci number
fibonacci series in python class 11
python program for n-th fibonacci number with code
write a program to print fibonacci series in python using while loop
fibonacci series in python w3schools
python program for n-th fibonacci number with code
python program for n-th fibonacci number code
python program for n-th fibonacci number
fibonacci series using recursion in python
nth fibonacci number formula
Python Program for n-th Fibonacci number
python program for n-th fibonacci number