I hate when people introduce recursion with something like this

deffib(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

deffib(n):if n <=1:return n
prev, curr =1,1for _ inrange(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 playdefminimax(board)->float:if board.game_over():return board.result()# X win = 1, O win = -1, tie = 0if board.side_to_move == X:# we are X, we want to maximize the resultreturnmax(minimax(child)for child in board.children())else:# we are O, we want to minimize the resultreturnmin(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