Ao desenvolver um programa ou algoritmo é comum repetir um pedaço do código algumas vezes. Para isso, na maioria dos casos, utilizamos as estruturas de repetição. Porém, os códigos podem ficar muito complexos utilizando essas estruturas. Por isso, temos a possibilidade de substituir as estruturas de repetição pela estrutura recursiva ou Recursão.

A recursão é bastante poderosa pois permite que uma função ou um procedimento possa ser definido dentro dele mesmo. Uma vez definidos, você pode executá-los várias vezes. Isso acontece, pois, a chamada do módulo ou da função acontece dentro deles mesmos.

DEFINIÇÃO DA RECURSÃO

A recursão faz a chamada de uma função ou procedimento como parte de sua própria definição. A chave do funcionamento dela é garantir que existe uma condição que faça eles pararem.

Neste caso, acontece a execução de uma ação que não é recursiva pela mesma função ou procedimento, ou seja, na ação da parada, não se chama a função ou o procedimento recursivo novamente.

De forma direta ou indireta, há controle de fluxo do algoritmo, de forma que uma função ou procedimento chama a si mesmo(a).

Se uma função ou procedimento faz a própria chamada, a execução também chama a si mesma e assim por diante, de forma contínua e sem fim. Esse acontecimento denomina-se recursão infinita, que é parecida com os erros quando se usa a estrutura de repetição, que deixam o programa rodar infinitamente.

Para que você não tenha recursão infinita em seus algoritmos, ela precisa ser criada de forma que você garanta que, em algum momento do programa, seja finalizada sem se chamar novamente.

Exemplo para o cálculo do fatorial de um número:

se n = 0, então o fat(n) é 1

caso contrário, fat(n) = n * fat(n-1)

REGRAS DA RECURSÃO

Ao desenvolver uma recursão, você precisa garantir a aplicação das três regras a seguir:

1. Saber quando parar.
2. Decidir como fazer a próxima ação.
3. Quebrar uma jornada recursiva em um passo mais uma jornada recursiva menor.

A primeira regra é a checagem para garantir que a recursão chegou ao fim, antes de tomar a decisão de ir para a outra jornada recursiva.

Na função do fatorial, se n = 0, então a recursão é encerrada, devolvendo o valor 1 de fat(0).

A segunda regra é uma forma de garantir que o problema seja quebrado em partes menores e mais fáceis de resolver.

Na função fatorial, se n > 0, então a recursão vai devolver n * fat(n-1), a chamada recursiva se chama, porém, passando como parâmetro um número menor.

A terceira regra permite que a recursão se chame novamente, com um problema menor. Veja como fica:

fat(n)
n * fat(n-1)
n * (n-1) * fat(n-2)
…
n * (n-1) * … * fat(2)
n * (n-1) * … * 2 * fat(1)
n * (n-1) * … * 2 * 1 * fat(0)
n * (n-1) * … * 2 * 1 * 1