A recursividade é um recurso muito importante para a programação, é uma maneira de se visualizar uma solução para determinado problema. Há diversas vantagens no uso da recursividade, tais como o estudo da complexidade algorítmica, visualização do algoritmo etc. Porém a recursividade pode causar rompimento na pilha de memória.

Para exemplificar com funciona a recursividade simples utilizaremos o algoritmo do cálculo do MDC pelo método de Euclides. Em linguagem algorítmica seria algo como:

Algoritmo EuclidesMDC
|  {Faz o cálculo do MDC seguindo Euclides}
|início
|
|função calculoMDC(valorA: inteiro, valorB: inteiro): inteiro
||início
||     se valorB = 0 então
||     |      calculoMDC <- valorA
||     |senão
||     |      calculoMDC <- calculoMDC(valorB, valorA mod valorB)
||     fim-se
|fim-função
fim

O Algoritmo de Euclides nada mais faz que pegar dois números e dividí-los, o resto da divisão de A por B é testado se for zero, então o algoritmo retorna o menor valor como sendo o MDC, se for diferente de zero, o maior valor é jogado no caso A e B assume seu lugar, o resto da divisão de A por B assume o lugar de B e a função é chamada novamente até que o resto da divisão seja zero.

Faça o teste de mesa e verá que o algoritmo proposto apesar de simples cobre grande parte dos casos. Só não funcionará para números negativos pois "mod" não está definido para eles, segundo a matemática discreta.