Find Nth Fibonacci Number


Nth Fibonacci Number

To find the Nth Fibonacci number, we can use Recursion technique or a For Loop.

In this tutorial, we will write Python programs that cover both of the above said techniques to find out Nth Fibonacci number.

1. Nth Fibonacci Number using Recursion

In the following program, we write a function fibonacci() that can take n as argument, and return the nth Fibonacci number. This fibonacci() is a recursion function.

Algorithm for fibonacci(n)

We have to consider that the first and second elements of a Fibonacci series are 0 and 1 respectively. And any element after these two elements is the result of adding the previous two numbers.

Now the algorithm is

  1. If n is less than zero, print message "Invalid n".
  2. If n is 1, return 0.
  3. If n is 2, return 1.
  4. If n is greater than 2, return the sum of fibonacci(n-1) and fibonacci(n-2).

Input

n, where n > 0

Python Program

def fibonacci(n) :
    if n < 0:
        print('Invalid n')
        return
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

n = int(input('Enter n : '))
result = fibonacci(n)
print(f'{n}-Fibonacci Number : {result}')

Output

Enter n : 10
10-Fibonacci Number : 34

2. Nth Fibonacci Number using For Loop

In the following program, we write a function fibonacci() that can take n as argument, and return the nth Fibonacci number.

Algorithm for fibonacci(n)

We have to consider that the first and second elements of a Fibonacci series are 0 and 1 respectively. And any element after these two elements is the result of adding the previous two numbers, and we shall use For Loop in this example.

Now the algorithm is

  1. If n is less than zero, print message "Invalid n".
  2. If n is 1, return 0.
  3. If n is 2, return 1.
  4. If n is greater than 2, use For Loop in the range of (2, n) to compute fibonacci series, and returning the lat element.

Input

n, where n > 0

Python Program

def fibonacci(n) :
    if n < 0:
        print('Invalid n')
        return
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        a = 0 #previous element
        b = 1 #previous to previous element
        c = 0 #current element
        for i in range(2, n):
            c = a + b
            a = b
            b = c
        return c

n = int(input('Enter n : '))
result = fibonacci(n)
print(f'{n}-Fibonacci Number : {result}')

Output

Enter n : 10
10-Fibonacci Number : 34

Summary

In this tutorial of Python Examples, we learned how to find the Nth Fibonacci number, where N is given, with examples.