Recursão

RECURSÃO

Em primeiro lugar, vamos analisar o conceito de recursão e depois examinaremos vários programas

Uma função recursiva é chamada para resolver o problema. Na realidade, a função só sabe resolver os casos mais simples, os chamados casos básicos. Se a função for chamada em um problema mais complexo, ela divide o problema em duas partes teóricas: uma parte que a função sabe como resolver e outra que ela não sabe.

Para tornar viável a recursão, a segunda parte deve ser parecida com o problema original, mas ser uma versão um pouco mais simples ou menor do que ele. Por esse novo problema ser parecido com o problema original, a função chama uma nova cópia de si mesma para lidar com o problema menor – o que é conhecido por chamada recursiva ou etapa de recursão.

A etapa de recursão também incluiu a palavra-chave return porque seu resultado será combinado com a parte do problema que a função sabe como resolver para formar um resultado que será enviado de volta para a função original de chamada, possivelmente main.

A etapa de recursão é executada enquanto a chamada original para a função estiver ativa, i.e., ainda não tiver sido concluída. A etapa de recursão pode levar a outras chamadas recursivas, à medida que a função continuar a dividir cada problema em duas partes conceituais.

Para a recursão chegar ao fim, cada vez que a função chamar a si mesma com uma versão ligeiramente mais simples do problema original, essa sequencia de problemas cada vez menores deve convergir posteriormente para o caso básico.

Nesse instante, a função reconhece o caso básico, envia um resultado de volta para a cópia anterior da função e ocorre uma sequencia de remessa de resultados na ordem inversa até a chamada original da função enviar mais tarde o resultado final para main.

Tudo parece um tanto esquisito, se comparado com a maneira convencional de resolver problemas que usamos até aqui. Na verdade, é necessário muita pratica com programas recursivos antes de o processo parecer natural.