There are several methods to find the nth Fibonacci number in Python. These are as follows:
Of these methods, the two most basic are the Dynamic method and recursion.
Let’s take a deeper look at how each of these methods works.
Recursion defines something within itself. In Python, recursion refers to the process of a function calling itself. With the correct code recursion will create a finite loop.
In the code below:
0
& 1
.n=1
or n=2
(1st or 2nd Fibonacci numbers), we use an if-else statement to return 0
or 1
.n
is greater than 2
, The function calls itself with a lower input value. As you see in the code, it returns (fibonacci(n-1)+fibonacci(n-2))
.n=1
and n=2
, and as we know from before, n=1
returns 0
and n=2
returns 1
.def Fibonacci(n): if n<0: print("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(n-1)+Fibonacci(n-2)) print(Fibonacci(10))
Dynamic programming uses recursion too, but it mainly uses if-else statements. In the statements, a variable is used to store the value of the Fibonacci number. This Fibonacci number is obtained by repeated addition which is obtained using recursion. In the given program, the storage variable is named ‘x’.
In the code below:
FibArray
with elements 0
& 1
in its 0
& 1
2
(i.e., the length of the array FibArray
), it returns 0
as the first number (n=1
) and 1
as the second number (n=2
).n
is greater than 2
, we use recursion to call and add the previous 2 elements (similar to the first code).FibArray
array. Finally, we return the last element of the array (the nth element).def fibonacci(n): # Taking 1st two fibonacci nubers as 0 and 1 fibArray = [0, 1] # Here, since we know that the first 2 fibonacci numbers are 0 and 1, we append the remaining values (Fibonacci numbers from index 2 to n) in the array using recursion and return the last element. # In the range function, we take range(2,n+1) instead of range(2,n). This is because range function in python iterates until the value before the upper limit. So, if we take from 2 to n, it would only iterate from 2nd to (n-1)th element. for i in range(2, n+1): fibArray.append(fibArray[i-1] + fibArray[i-2]) return fibArray[n] print(fibonacci(10))
This method is almost entirely the same as dynamic programming. However, dynamic programming uses recursion to achieve repeated addition, while this method uses the `for loop’.
In the code below:
a=0
and b=1
– they are the 1st & 2nd elements of the series.0
for input value n=1
and 1
for input value n=2
using if-else statements. If n
is greater than 2
, we take a ‘for’ loop of i
in range( 2,n). This range function means the loop starts with the value 2
and keeps iterating until the value n-1
.c
. This variable is used to store the sum of the previous two elements in the series.c
takes the value of a+b
, the value of a
is reassigned to b
. Subsequently, the value of b
is reassigned to the value of c
. To put it more simply, after c
becomes a+b
, a = b
and b = c
.b
, which stores the value of the nth Fibonacci number.# Similar to previous example, we take first 2 fibonacci numbers as 0 and 1. def fibonacci(n): a = 0 b = 1 if n < 0: print("Incorrect input") elif n == 0: return a elif n == 1: return b # In the previous example, 'recursion' was used to create a finite loop. Over her, we use a for loop insted in order to obtain the fibonacci series. else: for i in range(2,n+1): c = a + b a = b b = c return b print(fibonacci(10))
In this method, an array of size n
is created by repeated addition using the for loop
. Then, the nth element is returned.
In the code below:
We start by creating an array FibArray
of size n+1
– This is because, when we say nth Fibonacci number’, we start counting from 1
. But, the index of an array starts from 0
. Hence, we give an additional space because the nth Fibonacci number will have the index value n+1.
At the creation of the array, all values are ‘0’ by default. Hence, we leave the 1st number (index 0) and change the 2nd number (index 1) to the value 1
.
Now, we take a for loop
with the variable i
in range(2,n+1). As explained in the previous code, the loop will start with the value i=2
and end with the value i=n
.
Next, in the loop, we assign the value of each element of the array. The i-th
element’s value is equal to the sum of the previous two elements in that array.
As the loop iterates, each value of the array is filled.
Finally, after the loop terminates, the value with index n-1
is returned.
As explained before, The array index value starts from
0
, but we start counting from1
. Hence, when we say ’nth Fibonacci number’ or ’nth element of the array’, the element holds the index valuen-1
. So, we return then-1
index element instead of then
index element.
def fibonacci (n): #creating an array in the function to find the nth number in fibonacci series. [0,1,1,...] FibArray = [0] * (n+1) FibArray[1] = 1 #Over here, we are adding elements of the series to the array using addition of provious 2 elements. for i in range (2,n+1): FibArray[i] = FibArray[i-1] + FibArray[i-2] return FibArray[n] if __name__ == "__main__": print(fibonacci (10))
RELATED TAGS
CONTRIBUTOR
View all Courses