Learn Python – Python program to find the nth Fibonacci Number- Basic and advance

In the following tutorial, we will understand how to locate the nth Fibonacci Number using Python. We can define a Fibonacci Number, where the following range is the sum of the previous two numbers.

The first two factors of the Fibonacci collection are 0 and 1, respectively. We can calculate the 0.33 factor of the series by adding the previous two factors and will get the third term as 0 + 1, which is equal to 1. Similarly, the fourth term will be the sum of the 2d and 0.33 terms, which is 1 + 1 = 2 and so on. The series of such numbers is regarded as a Fibonacci Series.

The recurrence relation defines a Fibonacci range as proven below:

Fn = Fn – 1 + Fn – 2

There are one-of-a-kind ways to discover the nth Fibonacci Number the usage of 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

Of these ways, the two most imperative are the Recursion method and the Dynamic method.

Let us apprehend the working of these strategies in element with examples.

Finding nth Fibonacci Number using Recursion

The time period recursion is used to define some thing within itself. In a programming language like Python, Recursion refers to the process of a characteristic calling itself. With the desirable and correct code, the Recursion will create a finite loop.

Let us reflect onconsideration on the following snippet of code for better understanding.

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 above snippet of code, we have described a characteristic as Fibonacci_Series() that accepts a parameter as n.

Moreover, we are conscious that the first two elements of the Fibonacci are 0 and 1. In the event of the input as n = 1 or n = 2 (First or Second phrases of Fibonacci series), we have used the if-else conditional declaration to return zero or 1. In case the fee of n is larger than 2, the function will call itself with a decrease input value. As we can study that the code returns (Fibonacci_Series(n – 1) + Fibonacci_Series(n – 2)). Here, the function calls itself with a decrease cost unless it reaches the base fee of n = 1 and n = 2, and as we know from before, n = 1 returns 0 and n = 2 returns 1. The returned values are then continually added to produce the sequence of the Fibonacci Series.

Finding the nth Fibonacci Number the use of Dynamic Programming

Dynamic Programming makes use of Recursion as well; however, it broadly speaking utilizes if-else conditional statements. Within the statements, the price of the Fibonacci number is saved in a variable. With the help of Recursion, the repeated addition permits us to obtain this Fibonacci number.

Let us reflect onconsideration on the following instance to recognize the same.

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 above snippet of code, we described the feature as Fibonacci_series(), which accepts the parameter as variable x. We created a one-dimensional array as fib_Array with records factors zero and 1 in its zeroth and first indices. Then, if the furnished enter (‘x’) is less than or equal to 2, which is additionally the length of the array fib_Array, it returns zero as the first range for x = 1 and 1 as the 2d variety for x = 2 If the fee of x is larger than 2, we have used recursion to call and insert the previous two statistics elements. However, instead than returning the nth Fibonacci quantity directly, we append each of the summated factors to the fib_Array array. At last, we have back the last issue of the array (i.e., the nth element) and printed the price for the users.

Finding the nth Fibonacci Number using Dynamic Programming and Space Optimization

This method is nearly definitely same to Dynamic Programming. However, dynamic programming utilizes recursion to accomplish ordinary addition, whereas this approach utilizes the for-loop.

Let us consider the following instance to understand the same.

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 above snippet of code, we have described a feature and assigned two variables, m = zero and n = 1. These elements are the first and 2nd factors of the Fibonacci Series. We have then used the if-elif-else conditional statements where the program returns zero for input cost x = 1 and 1 for input price x = 2 If the fee of x is higher than 2, we have used the for-loop of i in the range (2, x + 1). We have taken a variable o to store the sum of the previous two elements in the series. Once o takes the price of m + n, the cost of m is reassigned to n. Subsequently, the fee of n is reassigned to the cost of o. This procedure continues, and cost three keeps reassigning until the loop terminates. Once the loop is terminated, the feature returns the fee of n, which shops the fee of the nth Fibonacci Number.

Finding the nth Fibonacci Number using Array

In this method, we create an array of size x by way of repeated addition using the for-loop. Hence, the nth Fibonacci Number is returned.

Let us think about the following instance to recognize the same.

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 above snippet of code, we have described the function. Within the function, we have created an array to locate the nth element of the Fibonacci Series. We have then used the for-loop to add factors of the sequence to the array by means of repeating the addition of the previous two elements. At last, the nth issue is lower back and printed for the users.