Python program to find the nth Fibonacci Number

To find the nth Fibonacci number in Python, we can use various approaches such as iteration, recursion, or even more advanced methods like matrix exponentiation. Let’s explain a simple iterative approach, step by step:

What is the Fibonacci sequence?

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

The sequence looks like this:

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

In mathematical terms:

• F(0)=0F(0) = 0F(0)=0
• F(1)=1F(1) = 1F(1)=1
• F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2) for n≥2n \geq 2n≥2

Python Code Example: Iterative Approach

def fibonacci(n):
    # Check if the input is valid
    if n < 0:
        return "Invalid input! Fibonacci sequence is not defined for negative numbers."
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    
    # Initialize the first two Fibonacci numbers
    a, b = 0, 1
    
    # Calculate the nth Fibonacci number
    for _ in range(2, n + 1):
        a, b = b, a + b
    
    return b

# Test the function
nth_fib = 10  # Example: Find the 10th Fibonacci number
print(f"The {nth_fib}th Fibonacci number is: {fibonacci(nth_fib)}")

Detailed Explanation

1. Base Cases:
   • If n=0n = 0n=0, return 0 because the 0th Fibonacci number is 0.
   • If n=1n = 1n=1, return 1 because the 1st Fibonacci number is 1.
2. Initialization:
   • Start with the first two numbers in the Fibonacci sequence:
     • a = 0 (F(0))
     • b = 1 (F(1))
3. Iterative Calculation:
   • Use a loop to calculate the Fibonacci numbers up to the nth term.
   • For each step in the loop, update:
     • a to hold the value of b (previous number)
     • b to hold the sum of a and b (next Fibonacci number)
4. Return the Result:
   • After the loop, b contains the nth Fibonacci number.

Example Walkthrough

Let’s calculate the 5th Fibonacci number (n=5n = 5n=5) using the program:

1. Start with:
   • a = 0, b = 1
2. Loop iterations:
   • Iteration 1: a = 1, b = 1 (F(2) = 1)
   • Iteration 2: a = 1, b = 2 (F(3) = 2)
   • Iteration 3: a = 2, b = 3 (F(4) = 3)
   • Iteration 4: a = 3, b = 5 (F(5) = 5)
3. Final result: b = 5

Output: The 5th Fibonacci number is: 5

Important Points

• Efficiency: The iterative solution runs in O(n) time complexity with O(1) space complexity; it is very efficient for larger n.
• Readability: It is outright and does not incur the overhead of recursive function calls.