Repository navigation
Expand file tree
/
Copy pathfibonacci.py
More file actions
102 lines (68 loc) · 2.55 KB
/
Copy pathfibonacci.py
File metadata and controls
102 lines (68 loc) · 2.55 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
"""Fibonacci.
A sequence that starts with `[0, 1]`. Each additional number is the sum of the last two numbers.
Example: `[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...]`
`fibonacci(5) -> 5`
"""
from collections.abc import Generator
from functools import cache
def fibonacci(number: int, memo: dict[int, int] | None = None) -> int:
"""Generate the fibonacci number for n
Uses a dictionary to store previously computed values
0, 1, 1, 2, 3, 5, 8, 13, .... 0 = 0 , 1 = 1, 3 = 2, etc
:param number: iteration of the Fibonacci sequence
:param memo: memoization store, will be cached since it is mutable
:return: Fibonacci number
"""
if not memo:
memo = {0: 0, 1: 1}
if number not in memo:
memo[number] = fibonacci(number - 1, memo) + fibonacci(number - 2, memo)
return memo[number]
@cache
def fibonacci2(number: int) -> int:
"""Generate the fibonacci number for n
Utilizes caching to mimic literal memoization, has lower recursive limit...
0, 1, 1, 2, 3, 5, 8, 13, .... 0 = 0 , 1 = 1, 3 = 2, etc
:param number: iteration of the Fibonacci sequence
:return: Fibonacci number
"""
if number < 2: # noqa: PLR2004
return number
return fibonacci2(number - 1) + fibonacci2(number - 2)
def fibonacci3(number: int) -> int:
"""Generate the fibonacci number for n
iterative approach, no recursion constraints
0, 1, 1, 2, 3, 5, 8, 13, .... 0 = 0 , 1 = 1, 3 = 2, etc
:param number: iteration of the Fibonacci sequence
:return: Fibonacci number
"""
if number == 0:
return 0
last_nbr: int = 0
next_nbr: int = 1
for _ in range(1, number):
last_nbr, next_nbr = next_nbr, last_nbr + next_nbr
return next_nbr
def fibonacci_with_array(number: int, memo=None) -> int:
"""Generate the fibonacci number for n using an array-based memo, appending iteratively via recursion."""
if memo is None:
memo = [0, 1]
if len(memo) > number:
return memo[number]
memo.append(memo[-1] + memo[-2])
return fibonacci_with_array(number, memo)
def fibonacci_sequence(number: int) -> Generator[int]:
"""Generate the fibonacci number for n
Utilizes a generator
0, 1, 1, 2, 3, 5, 8, 13, .... 0 = 0 , 1 = 1, 3 = 2, etc
:param number: iteration of the Fibonacci sequence
:return: Fibonacci number Generator
"""
yield 0
if number > 0:
yield 1
last_nbr: int = 0
next_nbr: int = 1
for _ in range(1, number):
last_nbr, next_nbr = next_nbr, last_nbr + next_nbr
yield next_nbr