Calculates the first n (0-indexed) Fibonacci numbers using recursion >>> fib_recursive_cached(0) [0] >>> fib_recursive_cached(1) [0, 1] >>> fib_recursive_cached(5) [0, 1, 1, 2, 3, 5] >>> fib_recursive_cached(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_r
(n: int)
| 133 | |
| 134 | |
| 135 | def fib_recursive_cached(n: int) -> list[int]: |
| 136 | """ |
| 137 | Calculates the first n (0-indexed) Fibonacci numbers using recursion |
| 138 | >>> fib_recursive_cached(0) |
| 139 | [0] |
| 140 | >>> fib_recursive_cached(1) |
| 141 | [0, 1] |
| 142 | >>> fib_recursive_cached(5) |
| 143 | [0, 1, 1, 2, 3, 5] |
| 144 | >>> fib_recursive_cached(10) |
| 145 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] |
| 146 | >>> fib_recursive_cached(-1) |
| 147 | Traceback (most recent call last): |
| 148 | ... |
| 149 | ValueError: n is negative |
| 150 | """ |
| 151 | |
| 152 | @functools.cache |
| 153 | def fib_recursive_term(i: int) -> int: |
| 154 | """ |
| 155 | Calculates the i-th (0-indexed) Fibonacci number using recursion |
| 156 | """ |
| 157 | if i < 0: |
| 158 | raise ValueError("n is negative") |
| 159 | if i < 2: |
| 160 | return i |
| 161 | return fib_recursive_term(i - 1) + fib_recursive_term(i - 2) |
| 162 | |
| 163 | if n < 0: |
| 164 | raise ValueError("n is negative") |
| 165 | return [fib_recursive_term(i) for i in range(n + 1)] |
| 166 | |
| 167 | |
| 168 | def fib_memoization(n: int) -> list[int]: |
nothing calls this directly
no test coverage detected