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 begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. In this guide, we’ll write a Python program to find the nth Fibonacci number.
1. Using Iterative Approach
The iterative approach is straightforward and efficient for calculating the nth Fibonacci number. It avoids the overhead of recursion and is easy to understand.
1.1. Example: Iterative Approach
def fibonacci(n):
if n <= 0:
return "Invalid input. Please enter a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
a, b = 0, 1
for _ in range(3, n + 1):
a, b = b, a + b
return b
# Get the nth Fibonacci number
n = int(input("Enter the value of n: "))
print(f"The {n}th Fibonacci number is: {fibonacci(n)}")
In this example, the program iteratively calculates the nth Fibonacci number by starting with the first two numbers (0 and 1) and then calculating subsequent numbers until it reaches the nth number.
2. Using Recursion
Another way to find the nth Fibonacci number is by using recursion. This method is more intuitive but can be less efficient for large values of n
due to the repeated calculations.
2.1. Example: Recursive Approach
def fibonacci_recursive(n):
if n <= 0:
return "Invalid input. Please enter a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
# Get the nth Fibonacci number
n = int(input("Enter the value of n: "))
print(f"The {n}th Fibonacci number is: {fibonacci_recursive(n)}")
This example uses recursion to calculate the nth Fibonacci number. However, for large values of n
, this approach can be slow due to the exponential time complexity.
3. Using Dynamic Programming (Memoization)
Dynamic programming can be used to optimize the recursive approach by storing the results of subproblems and reusing them, reducing the time complexity to linear.
3.1. Example: Dynamic Programming (Memoization)
def fibonacci_memoization(n, memo={}):
if n <= 0:
return "Invalid input. Please enter a positive integer."
elif n in memo:
return memo[n]
elif n == 1:
memo[n] = 0
elif n == 2:
memo[n] = 1
else:
memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
return memo[n]
# Get the nth Fibonacci number
n = int(input("Enter the value of n: "))
print(f"The {n}th Fibonacci number is: {fibonacci_memoization(n)}")
This example uses a dictionary to store the results of subproblems, avoiding redundant calculations and significantly improving efficiency for large values of n
.
4. Example Output
Here’s an example of how the output might look when running the program:
Enter the value of n: 10
The 10th Fibonacci number is: 34
Conclusion
Finding the nth Fibonacci number can be done using different approaches, each with its pros and cons. The iterative method is the most efficient for small to medium values of n
, while dynamic programming (memoization) is more suitable for larger values. The recursive method is easy to understand but should generally be avoided for large inputs due to its inefficiency.