Fibonacci Sequence using Cache
lru_cache will store the result so we don’t have to find Fibonacci for the same num again.
Python3
from functools import lru_cache# Function for nth Fibonacci number@lru_cache(None)def fibonacci(num: int) -> int: # check if num is less than 0 # it will return none if num < 0: print("Incorrect input") return # check if num between 1, 0 # it will return num elif num < 2: return num # return the fibonacci of num - 1 & num - 2 return fibonacci(num - 1) + fibonacci(num - 2)# Driver Programprint(fibonacci(9)) |
Output
34
Time complexity: O(n)
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.