Signup/Sign In

Python Program for Nth Fibonacci Number

In this tutorial, we will learn how to compute the Nth Fibonacci Number. A Fibonacci number can be defined as such, where the next number is the sum of the previous two numbers.

The first two terms of the series are 0 and 1. The third term can be calculated by adding the previous terms, hence the third term is 1 (0 + 1). The fourth term will be the sum of the second and third terms which is 2 (1 + 1). The series of such numbers is called a Fibonacci series.

A Fibonacci number is defined by the recurrence relation:

Fn = Fn-1 + Fn-2

The first few numbers in the series are:

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

To compute nth Fibonacci number, we can follow two approaches:

  1. Using recursion

  2. Using list

Approach 1: Using recursion

For this approach, we will use the concept of recursion. Recursion is the process by which a function calls itself in the function definition. Look at the algorithm to take a closer look,

Algorithm

Step 1- Define a function fib_num() to find nth Fibonacci number

Step 2- Check if the number is positive

Step 3- If the number is less than or equal to 0 print "cant be computed"

Step 4- Else, check if the number is 1 return 0

Step 5- if the number is 2 return 1

Step 6- else recursively call the function

Step 7- Print the value returned by the function

Python Program

Look at the complete program given below to understand the implementation of the approach.

#recursive approach
def fib_num(n):
   if n<=0:
      print("Fibonacci can't be computed")
   # First Fibonacci number
   elif n==1:
      return 0
   # Second Fibonacci number
   elif n==2:
      return 1
   else:
      return fib_num(n-1)+fib_num(n-2)

#input
n=int(input("Enter n: "))
print("{}th Fibonacci number is ".format(n),fib_num(n))


Enter n: 4
4th Fibonacci number is 2
Enter n: 0
4th Fibonacci number is Fibonacci can't be computed

The .format() is a function for handling strings that permits you to do variable substitutions and data formatting. Here we have used this function to print the value of n in place of {} in the print statement.

Approach 2: Using lists

For this approach, we will be using the concept of the list and its function in Python. We will use the append() function of class NumPy in Python. The append() method adds values at the last of the existing list.

Algorithm

Step 1- Define a function fib_number() that will calculate nth Fibonacci number

Step 2- Check if the number is less than or equal to zero or not

Step 3- If true print "cant be computed"

Step 4- Else declare a list fib=[0,1] where 0 and 1 are the first two terms

Step 5- if n is greater than 2, run a loop from 2 to the number

Step 6- use append () to add the value of the next Fibonacci number in the list fib

Step 7- the next term(n) will be calculated as the sum of the (n-1)th term and (n-2)th term

Step 8- return the value of the nth term from the list

Step 9- Take input of the value n from the user

Step 10- pass the input as parameter in the function fib_number()

Python Progam

Look at the complete program given below to understand the implementation of the approach.

#list
def fib_number(n):
    if n<= 0:
        return "incorrect, can't be computed"
    else:
        fib = [0, 1]
        if n > 2:
         for i in range (2, n):
            fib.append(fib[i-1] + fib[i-2])
    return fib[n-1]
 
#input
n=int(input("Enter n: "))
print("{}th fibonacci number is: ".format(n),fib_number(n))


Enter n: 10
10th fibonacci number is: 34
Enter n: 0
0th fibonacci number is: incorrect, can't be computed

Conclusion

In this tutorial, we learned how to compute the Nth number of a Fibonacci series where n is given by the user. We have discussed two approaches in this article which you can follow for computing the Nth number of a Fibonacci series. The first approach was by defining a recursive function and the second was using lists in Python.