Introdução à recursividade

Ver Todos os Exercícios

Teoria

Introdução

Fala aí, aqui é o Guga do Responde Aí! Tudo bem com você?

Nesse tópico nós iremos conversar um pouco sobre recursividade, que nada mais é do que uma técnica de resolução de problemas grandes a partir da divisão deles em problemas menores.

Isso não parece estranho, né? Por exemplo, o que nós fazemos quando estamos sobrecarregados de tarefas?

Não... Nós não desistimos de tudo.

Nós simplesmente dividimos tudo o que temos para fazer em tarefas menores com objetivos mais claros. Por incrível que pareça, um computador também pode fazer isso as vezes.

Vem comigo!

Recursão

Para termos uma ideia mais clara sobre a recursividade, basta imaginarmos que um problema pode ser dividido consecutivamente até se tornar algo trivial. É justamente esse pensamento que as técnicas recursivas de resolução possuem como premissa.

Tá bom... Eu sei que você quer um exemplo.

Então, suponha que nós tenhamos que realizar uma soma com inúmeros elementos. Esses elementos estão armazenados em um vetor e caso estivessem explícitos na soma, teríamos algo assim:

3 + 7 + 3 + 1 + 9

Pode esquecer os laços de repetição para fazer uma varredura no vetor atualizando uma variável acumulativa, vamos fingir que eles não existem. Como resolveríamos esse problema?

Vamos tentar dividi-lo em soma menores!

3 + ( 7 + 3 + 1 + 9 )

Dá para dividir? Sim!

3 + ( 7 + ( 3 + 1 + 9 ) )

E agora, ainda dá para dividir? A resposta é sim!

3 + ( 7 + 3 + ( 1 + 9 ) )

Calma, agora chegamos em um problema trivial que é a soma de 1 e 9. Nós sabemos que o resultado é 10.

3 + ( 7 + 3 + 10 )

Ao substituirmos esse resultado, geramos outra soma trivial entre 3 e 10. Resolvendo, temos como resultado 13.

3 + ( 7 + 13 )

O mesmo acontece aqui... Já pegou, né? Para finalizar, esses seriam os últimos passos:

3 + ( 20 )

23

Você viu como ao dividir um problema até encontrarmos um problema menor e trivial fez com que, ao resolver o problema trivial, outros também triviais fossem surgindo?

Isso é o princípio da recursão!

Algoritmos recursivos

Agora que já entendemos a ideia de recursividade, vamos falar um pouco sobre os algoritmos recursivos. Não se preocupe, a ideia é a mesma.

Além da ideia de divisão, existem algumas peculiaridades nos algoritmos que utilizam a recursão como técnica de resolução de problema, mais especificamente 3 regras:

  • Deve ter um caso básico;
  • Deve se aproximar do caso básico a cada estado;
  • Deve chamar a si mesmo, recursivamente.

As coisas estão sem contexto? Então, imagine o problema do fatorial de um número. Como podemos resolvê-lo recursivamente?

A figura a seguir ilustra como isso pode ser feito:

Basicamente, uma função denominada Fat tem como parâmetro um número natural n. Caso esse número seja igual a 0, a função retorna 1. Caso contrário, ela utiliza-se da recursão para invocar a si mesma passando como parâmetro para a sua nova instância n – 1.

Isso acontecerá consecutivamente até que uma de suas instâncias receba como parâmetro n o valor 0, o que significa que o caso básico foi ativado, ou seja, o problema atingiu a sua instância trivial (no caso do fatorial, uma simples multiplicação). A partir desse momento, soluções básicas são retornadas de forma a voltar nas instâncias criadas gerando problemas triviais que são resolvidos até atingir a instância original, que por sua vez também será resolvida por uma operação também trivial.

A figura a seguir, exemplifica todo esse processo utilizando como exemplo o fatorial do número 4 e a criação de suas instâncias, bem como o retorno nelas ao atingir o caso básico:

Logo, podemos concluir que das regras anteriormente citadas, o caso básico sinaliza que o problema atingiu sua forma trivial e deve parar de criar instâncias e retornar nelas com soluções básicas que gerarão mais problemas triviais até resolver o todo. E que chamar a si mesmo é uma forma de criar instâncias e por sua vez se aproximar do caso básico.

Agora que você já sabe o que é recursividade, está na hora de exercitarmos o cérebro e resolvermos alguns exercícios de fixação!

Te espero aqui do ladinho.

Recursão

Algoritmos recursivos

Exercícios Resolvidos

Exercício Resolvido #1

Explique o que são algoritmos recursivos.

Passo 1

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.

Resposta

Na prática, quando falamos de algoritmos recursivos, estamos falando de uma função capaz de chamar ela mesma até atingir um caso básico. Após isso, ela retorna em suas chamadas realizando sucessivas soluções.

Exercício Resolvido #2

Identifique em uma função recursiva que, dado dois números inteiros x e n , calcula o valor de x n o caso básico e os passos de recursão que devem ser utilizados.

Passo 1

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 2 5 podemos dizer que isso é igual a 2 * 2 4 , que por sua vez é igual a 2 * 2 * 2 3 .

Tá, mas aonde queremos chegar?

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

Passo 2

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 x n = x * x n - 1 que passando para o nosso exemplo daria algo mais ou menos assim: 2 5 = 2 * 2 5 - 1 .

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #3

Um problema típico em ciência da computação consiste em converter um número da sua forma decimal para a forma binária. Identifique o caso básico de uma função recursiva capaz de resolver esse problema.

Passo 1

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.

Resposta

Isso acontece, pois, uma das formas possíveis para converter um número decimal para binário é fazer sucessivas divisões dele por 2 (ao mesmo tempo em que se analisa o resto dessa divisão) até que ele se torne 0 (convertido).

Exercício Resolvido #4

Observe a seguinte função recursiva:

Explique o que acontece quando a mesma é executada e realize um teste de mesa quando n = 3 .

Passo 1

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

Passo 2

Quando n = 3 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 f u n c 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 f u n c 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 f u n c passando 0 como parâmetro (linha 08);
  • 0 é igual a 0 (linha 03)? Sim, então imprime “Fim” (linha 04).

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #5

Qual é a importância de um caso básico em uma função recursiva?

Passo 1

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.

Resposta

Logo, além de não resolver o problema, uma função sem caso base nunca irá retornar na recursão e apenas irá criar mais instâncias.

Vai por mim... O computador iria travar mais rápido do que você imagina.

Exercício Resolvido #6

Mostre, através do teste de mesa, o resultado da seguinte função:

Considere a entrada f 1 ( 3 ) .

Passo 1

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

Passo 2

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

Passo 3

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 f 1 o valor 0.

Passo 4

Por fim, temo n 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 n é igual a 1, mas dessa vez sabemos o resultado de f 1 ( 0 ) e o programa saberá realizar a multiplicação n * f 1 ( n - 1 ) , pois a mesma é equivalente a 1 * 1 .

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

Passo 5

Estamos agora na instância em que n é igual a 2 e sabemos que f 1 1 = 1 , logo se temos n * f 1 ( n - 1 ) , sabemos o computador já sabe que isso é equivalente a 2 * 1 .

Passo 6

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

Resposta

Analisando o resultado obtido, isso nada mais do que o algoritmo para o cálculo do fatorial de um número através do uso de funções recursivas.

Exercício Resolvido #7

Mostre, através do teste de mesa, o resultado da seguinte função:

Considere a entrada f u n c ( 5 ) .

Passo 1

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 n (que armazena o valor 5) e 0. Como a condição é falsa, uma nova instância da função f u n c é criada, mas dessa vez com o parâmetro 4 ( n - 1 ).

Passo 2

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

Passo 3

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

Passo 4

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

Passo 5

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 n = 1 . Essa por sua vez, simplesmente imprimirá o valor de n (que é 1).

Passo 6

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

Resposta

Fazendo uma analise do algoritmo, o mesmo se trata de um código capaz de realizar uma contagem em ordem crescente utilizando de funções recursivas.

Exercício Resolvido #8

Dada a seguinte função recursiva e uma entrada a recebida como parâmetro:

Analise e responda qual é a execução esperada dessa função, ou seja, o resultado retornado.

Passo 1

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

Passo 2

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

Resposta

Ei, a resposta está no passo a passo :)