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

1. Actually a better upper bound is $O(\phi^n)$ see here.
2. Using lru_cache(maxsize=3) from functools makes it fast but still stack bounded (credit to ender)
3. 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)