Primeiro tenha certeza que entende o que é a pilha.
Ela é uma porção de memória previamente alocada pela aplicação que vai sendo preenchida conforme a necessidade das funções (ou escopos). Conforme a execução vai entrando em novos escopos ele vai reservando espaço (na parte já alocada) para todas variáveis locais contidas nele (isto é chamado de stack frame). Quando sai do escopo este espaço é liberado pelo movimentação de um ponteiro (stack pointer) que indica onde está o topo da pilha (a base dele na memória é indicado pelo base pointer e é usado para calcular o endereço real porque o acesso na pilha é sempre relativo ao seu início e não a memória toda). Então o espaço vai sendo usado em um efeito sanfona.

Se o código entrar em uma sequência grande de escopos - isto ocorre principalmente em chamada de funções - os espaços vão sendo reservados e não vão sendo liberados, até que comece sair destes escopos. A pilha tem um espaço finito, então uma hora pode não ter mais espaço alocado para reservar, e o estouro de pilha ocorre.
Isto pode ocorrer principalmente em duas situações:
- Alocações de dados muito grandes em variáveis locais (sem apontamento) - o que nunca é recomendado - que mesmo em uma única chamada de uma função pode reservar quase toda pilha alocada, deixando em um estado de quase estouro;
- Fazer chamadas recursivas sem parada, ou com parada muito distante, conforme colocado na pergunta, o que é mais comum.
No caso da recursão, mesmo com uma única variável simples de baixo consumo de memória é possível, em milhares de execuções, estourar a pilha (alguns compiladores conseguem fazer uma otimização eliminando a recursividade).
Neste caso a função fat()
terá sempre que reservar 4 bytes (tipicamente) para o parâmetro n
(que é uma variável local) e provavelmente mais 4 bytes para o retorno da função chamada. Se não tem nada que pare isto vai acumulando estes bytes indefinidamente em cada chamada.
O tamanho da pilha varia e, em geral, pode ser determinado no momento da criação do executável. O padrão usado pode variar também, mas é comum que a pilha tenha 1MB no Windows.
Quando vai criar threads uma nova pilha é criada. Isso pode ser muito, e em alguns casos, pouco. É possível controlar isso.
Coloquei no GitHub para referência futura.