Python Program for n-th Fibonacci number

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

    Fn = Fn-1 + Fn-2

with seed values

   F0 = 0 and F1 = 1.

Method 1 ( Use recursion ) : 

# Function for nth Fibonacci number

def Fibonacci(n):
    if n<0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==1:
        return 0
    # Second Fibonacci number is 1
    elif n==2:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)

# Driver Program

print(Fibonacci(9))

Output:

21 

Method 2 ( Use Dynamic Programming ) : 

# Function for nth fibonacci number - Dynamic Programing 

# Taking 1st two fibonacci nubers as 0 and 1 



FibArray = [0,1] 



def fibonacci(n): 

            if n<0: 

                       print("Incorrect input") 

            elif n<=len(FibArray): 

                       return FibArray[n-1] 

            else: 

                       temp_fib = fibonacci(n-1)+fibonacci(n-2) 

                       FibArray.append(temp_fib) 

                       return temp_fib 



# Driver Program 



print(fibonacci(9)) 

Output:
21 



Method 3 ( Use Dynamic Programming with Space Optimization) :

# Function for nth fibonacci number - Space Optimisataion
# Taking 1st two 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
    else:
        for i in range(2,n):
            c = a + b
            a = b
            b = c
        return b

# Driver Program

print(fibonacci(9))

Output:

21