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
- If n is less than zero, print message "Invalid n".
- If n is 1, return 0.
- If n is 2, return 1.
- 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
- If n is less than zero, print message "Invalid n".
- If n is 1, return 0.
- If n is 2, return 1.
- 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.