I hate when people introduce recursion with something like this

```
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2)
fib(6) # => 8
fib(35) # => 9227465
```

If you run this code yourself, you'll notice `fib(35)`

takes a long time to run, that's because fib gets called 29860703 times to compute `fib(35)`

.
which is exponential complexity! $O(2^n)$ [1]

Nobody should be taught recursion like this, the correct [2] way to write `fib(n)`

is

```
def fib(n):
if n <= 1: return n
prev, curr = 1, 1
for _ in range(n - 2):
prev, curr = curr, prev+curr
return curr
```

Harder to understand? Yes, but this is $O(n)$. so we can compute `fib(100_000)`

in an instant. [3]

The real time you use recursion is for traversing some kind of tree, ie. in minimax for solving tictactoe (psudocode)

```
# minimax gives the value of a board state, assuming perfect play
def minimax(board) -> float:
if board.game_over():
return board.result() # X win = 1, O win = -1, tie = 0
if board.side_to_move == X:
# we are X, we want to maximize the result
return max(minimax(child) for child in board.children())
else:
# we are O, we want to minimize the result
return min(minimax(child) for child in board.children())
```

Stop recursion abuse!

## Footnotes

- Actually a better upper bound is $O(\phi^n)$ see here.
- Using
`lru_cache(maxsize=3)`

from functools makes it fast but still stack bounded (credit to ender) - An explicit formula exists so you could say $O(\log n)$ is optimal (since it uses $2^n$ which takes $\log n$ time to compute using binary exponentiation)