Python Program for Fibonacci numbers using Recursion
Python Function to find the nth Fibonacci number using Python Recursion.
Python3
def Fibonacci(n): # Check if input is 0 then it will # print incorrect input if n < 0: print("Incorrect input") # Check if n is 0 # then it will return 0 elif n == 0: return 0 # Check if n is 1,2 # it will return 1 elif n == 1 or n == 2: return 1 else: return Fibonacci(n-1) + Fibonacci(n-2)# Driver Programprint(Fibonacci(9)) |
Output
34
Time complexity: O(2 ^ n) Exponential
Auxiliary Space: O(n)
Python Program to Print the Fibonacci sequence
The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. 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.