How to find the nth Fibonacci number in Python

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:

We are aware that the first two Fibonacci numbers are 0 & 1.
In the event of the input as n=1 or n=2 (1st or 2nd Fibonacci numbers), we use an if-else statement to return 0 or 1.
If 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)).
Here, the function calls itself with a lower value until it reaches the base value 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 continuously added to produce the sequence of the Fibonacci series.

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:

We start with a one-dimensional array; the FibArray with elements 0 & 1 in its 0th and 1st indicesbeing 0 & 1.
Then, if the given input (’n’) is less than or equal to 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).
If n is greater than 2, we use recursion to call and add the previous 2 elements (similar to the first code).
However, here, instead of returning the nth Fibonacci number directly, we append each of the summated elements to the 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:

We take 2 pre-assigned variables a=0 and b=1 – they are the 1st & 2nd elements of the series.
Then, we return 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.
Over here, we take a storage variable c. This variable is used to store the sum of the previous two elements in the series.
Consider the series to be quite literally in the sequence of a, b, & c. Once 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.
This process continues and value 3 keeps reassigning until the loop terminates.
Once the loop is terminated, the function returns the value of 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 from 1. Hence, when we say ’nth Fibonacci number’ or ’nth element of the array’, the element holds the index value n-1. So, we return the n-1 index element instead of the n index element.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to find the nth Fibonacci number in Python

1. Using recursion

2. Using dynamic programming

3. Using dynamic programming and space optimization

4. Using arrays