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)) #This code is contributed by Saket Modi |
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)) # |