In this tutorial, we will explore how to calculate the nth Fibonacci Number using Python. A Fibonacci Number is defined such that each number in the sequence is the sum of the two numbers that come before it.
The initial two numbers in the Fibonacci sequence are 0 and 1. To determine the third number in the sequence, we sum the two previous numbers, resulting in 0 + 1, which equals 1. In the same manner, the fourth number is derived from the second and third numbers, giving us 1 + 1 = 2, and this process continues. This sequence of numbers is referred to as the Fibonacci Series.
The Fibonacci number is defined by the recurrence relation presented below:
F n = F n - 1 + F n - 2
There are different ways to find the nth Fibonacci Number using the Python programming language. Some of them are as follows:
- Finding nth Fibonacci Number using Recursion
- Finding nth Fibonacci Number using dynamic programming
- Finding nth Fibonacci Number using dynamic programming and space optimization
- Finding nth Fibonacci Number using arrays
Among these approaches, the two most essential are the Recursion method and the Dynamic method.
Let’s explore how these techniques function in depth, accompanied by examples.
Finding nth Fibonacci Number using Recursion
Recursion is a term that describes a concept defined in relation to itself. In programming languages such as Python, recursion pertains to the mechanism by which a function invokes itself. When implemented correctly, the recursion will produce a finite loop.
We will explore the subsequent example to illustrate the method for calculating the nth Fibonacci Number through the use of Recursion.
Example:
# defining the function for Fibonacci Series
def Fibonacci_Series(n):
# using if-else conditional statement
if n < 0:
print("Oops! Incorrect input")
# First Fibonacci number is 0
elif n == 0:
return (0)
# Second Fibonacci number is 1
elif n == 1:
return (1)
else:
return (Fibonacci_Series(n - 1) + Fibonacci_Series(n - 2))
# printing the 12th element of the Fibonacci Series
print("12th Element of the Fibonacci Series:", Fibonacci_Series(12))
Output:
12th Element of the Fibonacci Series: 144
Explanation:
In the preceding code segment, we have established a function named Fibonacci_Series that takes a parameter denoted as n.
Additionally, it is important to note that the initial two numbers of the Fibonacci sequence are 0 and 1. When the input is n = 1 or n = 2 (representing the First or Second terms of the Fibonacci series), we utilize an if-else conditional structure to yield 0 or 1, respectively. For values of n exceeding 2, the function invokes itself with a reduced input. As demonstrated, the code computes (FibonacciSeries(n - 1) + FibonacciSeries(n - 2)). This recursive function continues to call itself with decrementing values until it arrives at the base cases of n = 1 and n = 2. As established earlier, n = 1 results in 0 and n = 2 results in 1. The values returned are then aggregated to generate the Fibonacci Series.
Finding the nth Fibonacci Number using Dynamic Programming
Dynamic Programming also employs Recursion, but it predominantly relies on if-else conditional statements. Inside these statements, a variable is used to store the value of the Fibonacci number. By leveraging Recursion, the process of repeated addition enables us to calculate this Fibonacci number.
To illustrate the method of obtaining the nth Fibonacci Number through Dynamic Programming, we will examine the subsequent example.
Example:
# defining the function to find the nth Fibonacci Number
def Fibonacci_series(x):
# Taking First two terms of the Fibonacci Series as 0 and 1
fib_Array = [0, 1]
# Here, as we know that the first two terms of Fibonacci Series are 0 and 1,
# we append the remaining values (Fibonacci numbers from index 2 to x)
# in the array using recursion and return the last element.
# In the range function, we take range(2, x + 1) instead of range(2, x).
# This is because range function in python iterates until the value
# before the upper limit. So, if we take from 2 to x, it would only
# iterate from second to (x - 1)th element.
for n in range(2, x + 1):
fib_Array.append(fib_Array[n - 1] + fib_Array[n - 2])
return fib_Array[x]
print("12th Term of Fibonacci Series:", Fibonacci_series(12))
Output:
12th Term of Fibonacci Series: 144
Explanation:
In the code snippet provided, we established the function named Fibonacciseries, which takes a parameter referred to as x. We initialized a one-dimensional array called fibArray containing the first two elements, 0 and 1, at indices zero and one, respectively. Next, if the input value ('x') is less than or equal to 2, which corresponds to the current length of the fibArray, the function returns 0 for x = 1 and 1 for x = 2. If x exceeds 2, we employ recursion to compute and include the two preceding elements. Instead of directly returning the nth Fibonacci number, we append the results of the summed elements into the fibArray. Ultimately, the function returns the last element of the array (i.e., the nth Fibonacci number) and displays this value to the user.
Finding the nth Fibonacci Number using Dynamic Programming and Space Optimization
This approach closely resembles Dynamic Programming. Nonetheless, while dynamic programming employs recursion to perform repeated summation, this method makes use of a for-loop instead.
To illustrate the process of determining the nth Fibonacci Number through Dynamic Programming and Space Optimization, we can examine the following example.
Example:
# defing the function to return the nth element of the Fibonacci Series
def Fibonacci_series(x):
# assiging the variables
m = 0
n = 1
# using the if-elif-else conditional statements
if x < 0:
print("Wrong input")
elif x == 0:
return m
elif x == 1:
return n
else:
# using the for-loop
for i in range(2, x + 1):
o = m + n
m = n
n = o
return n
# printing the twelveth term of the Fibonacci Series
print("12th element of the Fibonacci Series:", Fibonacci_series(12))
Output:
12th element of the Fibonacci Series: 144
Explanation:
In the code snippet provided, a function is established, and two variables are initialized with m = 0 and n = 1. These variables represent the first two numbers in the Fibonacci Sequence. The code then employs if-elif-else conditional statements, where it outputs 0 when the input value x equals 1, and 1 when x equals 2. For values of x exceeding 2, a for-loop iterates over the range from 2 to x + 1. A variable o is utilized to accumulate the sum of the two preceding numbers in the sequence. When o is set to m + n, the value of m is updated to n. Following that, n is updated to the value of o. This cycle persists, with value 3 being reassigned continuously until the loop concludes. After the loop completes, the function returns the value of n, which contains the nth Fibonacci Number.
Finding the nth Fibonacci Number using Array
This technique involves generating an array of size x through iterative addition with the for-loop. As a result, the nth Fibonacci Number is yielded.
To illustrate the process of determining the nth Fibonacci Number through the use of Arrays, let us examine the subsequent example.
Example:
# defining the function
def Fibonacci_series(x):
# creating an array in the function
fib_Array = [0] * (x + 1)
fib_Array[1] = 1
# adding elements of the series to the array using addition of previous two elements.
for n in range (2, x + 1):
fib_Array[n] = fib_Array[n - 1] + fib_Array[n - 2]
return fib_Array[x]
if __name__ == "__main__":
print("12th element of the Fibonacci series:", Fibonacci_series(12))
Output:
12th element of the Fibonacci series: 144
Explanation:
In the code snippet provided above, a function has been established. Inside this function, an array is initialized to determine the nth element of the Fibonacci Series. A for-loop is subsequently utilized to populate the array by continuously summing the two previous elements. Finally, the nth element is returned and displayed for the users.
