Introdução à recursividade

Algoritmos recursivos são aqueles algoritmos que pegam um problemão e vão dividindo, dividindo, dividindo esse problemão até ele se torne um probleminha e possa ser resolvido de forma simples, usando essa solução para resolver outra divisão até que o problema todo esteja resolvido.

Para descobrirmos o caso básico temos que pensar como podemos subdividir um problema de potência e onde essas divisões devem parar.

Usando como exemplo a potência podemos dizer que isso é igual a , que por sua vez é igual a .

Tá, mas aonde queremos chegar?

No caso mais trivial possível que é: . Ou seja, temos uma solução simples quando o problema é subdividido a ou nesse caso e por esse motivo esse é o nosso caso básico.

O passo de recursão, por sua vez, é a forma como vamos subdividir o problema para atingir problemas cada vez menores.

Mas calma, nós não já descobrimos isso?

Logo, podemos dizer que o passo de recursão utilizado foi que passando para o nosso exemplo daria algo mais ou menos assim: .

O caso básico é quando um problema já atingiu a sua forma trivial, no caso da conversão de um número de sua forma decimal para binária podemos dizer que o caso básico é esse número se tornar 0.

Se trata de uma função recursiva que recebe um número inteiro como parâmetro e chama instâncias de si mesma (passando como parâmetro ) para realizar uma contagem decrescente desse número até 0 (sendo esse o caso básico que marca o fim da função).

Quando a função irá se comportar da seguinte forma:

• 3 é igual a 0 (linha 03)? Não, então imprime 3 (linha 07) e chama a função passando 2 como parâmetro (linha 08);
• 2 é igual a 0 (linha 03)? Não, então imprime 2 (linha 07) e chama a função passando 1 como parâmetro (linha 08);
• 1 é igual a 0 (linha 03)? Não, então imprime 1 (linha 07) e chama a função passando 0 como parâmetro (linha 08);
• 0 é igual a 0 (linha 03)? Sim, então imprime “Fim” (linha 04).

Se uma função recursiva for executada sem um caso básico, o computador irá tentar subdividir o problema que está sendo resolvido infinitamente. Ou seja, não vai ter um caso que vai dizer para o computador quando ele deve parar de criar instâncias e começar a retornar.

Sendo 3 o dado recebido como parâmetro e a variável local que armazenará esse valor, a primeira coisa que irá ocorrer é a verificação de igualdade entre e 0 (linha 03). Como é igual a 3 (diferente de 0) o bloco que será executado é else, esse por sua vez cria uma instância da função passando como parâmetro o número 2 ().

Já na nova instância temos armazenando o valor 2, como 2 ainda é diferente de 0, outra instância de é criada (dessa vez passando o valor 1 como parâmetro).

O mesmo ocorre aqui, pois 1 ainda é diferente de 0, o que faz com que outra instância seja criada passando como parâmetro de o valor 0.

Por fim, temo igual a 0, isso faz com que o nosso caso básico seja verdadeiro e o valor 1 seja retornado para a instância anterior.

Estamos agora novamente na instância em que é igual a 1, mas dessa vez sabemos o resultado de e o programa saberá realizar a multiplicação , pois a mesma é equivalente a .

O resultado, que também é 1, será retornado para a instância anterior.

Estamos agora na instância em que é igual a 2 e sabemos que , logo se temos , sabemos o computador já sabe que isso é equivalente a .

Por fim, estamos na primeira instância criado, aquela em que é igual a 3. Porém, dessa vez sabemos que , logo, se temos que é equivalente a , o computador simplesmente realizará uma multiplicação de que é igual a 6.

Considerando que a função recebe como parâmetro o valor 5, a primeira coisa que o programa executa é a verificação de igualdade entre (que armazena o valor 5) e 0. Como a condição é falsa, uma nova instância da função é criada, mas dessa vez com o parâmetro 4 ().

Sendo igual a 4 nessa nova instância, a mesma verificação será executada (já que é a mesma função) e como ainda é diferente de 0, outra instância é criado passando como parâmetro o valor 3.

Essas novas instâncias serão criadas até que o caso básico seja verdadeiro, ou seja, . Mas para isso, além das instâncias onde é igual a 5 e 4 (descritas nos passos anteriores) outras foram criadas, mais precisamente aquelas em que é igual a 3, 2, 1 e por fim 0.

Considerando que estamos na instância em que , a verificação de caso básico será verdadeira e a palavra “Fim” será impressa na tela com uma quebra de linha.

Após a impressão, está na hora da função retornar em suas instâncias, nesse caso o primeiro retorno será para a instância em que . Essa por sua vez, simplesmente imprimirá o valor de (que é 1).

Mais retornos recursivos ocorrerão, dessa vez estamos na instância em que , logo, o valor 2 será impresso e depois o 3, 4 e por fim 5 (primeira instância criada).

Essa função tem o objetivo de usar a recursão para realizar o cálculo da soma do número recebido como parâmetro com seus antecessores.

Isso acontece, pois cada retorno de instância passando (antecessor da instância atual) como parâmetro será somado com . Logo, teremos a soma de com todos os seus antecessores até 0 (que é o caso básico limitante).