Algoritmos: Entendendo Recursividade
Neste post falaremos sobre um tópico crucial para resolução e entendimento de alguns dos principais algoritmos computacionais: a recursão ou recursividade.
Em resumo, esse post falará sobre os seguintes tópicos:
- Recursividade;
- Dividir e conquistar;
- Pilha de Chamada .
De maneira objetiva e resumida, a recursão é uma forma de uma rotina (função) chamar a si mesma, porém com inputs diferentes.
Mas, se ficou confuso ou quer entender melhor na prática, continue lendo a seguir :).
Recursão: Dividir e conquistar
A ideia de dividir e conquistar consiste em quebrar um problema grande em partes menores (dividir), resolvê-los e por meio das soluções, resolver um problema maior (conquistar).
Podemos resumir em três principais passos:
- Dividir: Divida o problema em subproblemas menores, até encontrar o caso base;
- Conquiste os subproblemas: resolva cada problema menor de forma isolada;
- Recombine a resolução dos subproblemas: por meio das resoluções dos problemas menores, resolva o maior.
Dividindo um problema
A recursão é uma ideia que permite que um problema maior seja resolvido em instâncias menores.
A parte de dividir em subproblemas seria a parte em que fazemos o passo 1: dividir.
Mas isso ainda não nos diz muito como solucionar um problema utilizando essa ideia. Vamos entender melhor mostrando um problema real utilizando recursão.
Antes de prosseguirmos, vamos levar o conceito para o lado da computação: os algoritmos recursivos chamam a si mesmos , porém passando parâmetros diferentes (que em tese são a “instância menor” do que algoritmo irá resolver).
Geralmente, cada vez que chamamos a própria função com parâmetros diferentes podemos considerar que é um subproblema a ser resolvido.
Vamos entender finalmente o processo de dividir um problema utilizando um exemplo clássico: o fatorial de um número.
Exemplo de como subdividir um problema: Fatorial
Segundo o wikipedia: “Na matemática, o fatorial de um número natural n, representado por n!, é o produto de todos os inteiros positivos menores ou iguais a n.”
Na prática, isso significa que se queremos descobrir o fatorial de 4 (4!), devemos fazer:
4! = 4 x ( 4–1) x (4–2) x (4–3)4 = 4 x 3 x 2 x 1 = 24.
O fatorial de 5 então, seria:
5! = 5 x (5–1) x (5–2) x (5–3) x (5–4)E assim por diante…
Outra ótica para este problema é “quebrá-los” em porções de fatoriais menores.
Se você reparar bem, um fatorial de um número é o próprio número menos o fatorial do número menos um. Mas como assim?
Para simplificar:
4! = 4 x 3! (o fatorial de 4, é 4 vezes o fatorial de 3)3! = 3 x 2! (o fatorial de 3 é 3 vezes o fatorial de 2)2! = 2 x 1! (o fatorial de 2 é 2 vezes o fatorial de 1)1! = 1 x 0! (o fatorial de 1 é 1 vez o fatorial de 0)0! = o fatorial de zero é 1
Esta é exatamente a forma recursiva de se pensar como quebrar um problema.
- Dividimos o problema em fatoriais menores até chegar no fatorial de zero.
Porém, vale fazer uma ressalva. Imagine que por algum motivo, não temos um erramos ao descrever o caso base do nosso problema. Em que isso implicaria?
Os subproblemas ficariam infinitamente sendo criados e nunca seriam resolvidos.
Então precisamos parar de chamá-lo em algum momento, caso contrário, nunca conseguiremos resolver o problema pois, estaremos em um loop infinito criando mais e mais subproblemas.
O momento que paramos de chamá-lo também é conhecido como caso base. Em nosso exemplo acima, o caso base é quando chegarmos ao fatorial de zero (0!).
À nível de programação, se não tivermos um caso base haverá um problema de estouro de pilha (stack overflow) ou de memória, pois como entenderemos posteriormente, até resolvermos o caso base precisamos manter todas as chamadas com suas respectivas variáveis em memória (os recursos de memória/pilha de chamada de um programa não são infinitos).
Por isso, ao chamar ad infinitum uma função, teremos um estouro de pilha ou memória.
Se você não conhece ou não lembra como uma pilha de chamada funciona, escrevi um resumo no final desse post em Apêndice: Pilha de Chamada. Dá uma olhada se houver curiosidade e depois volta aqui e prossiga a leitura :).
Conquistar
Seguindo o exemplo do problema do fatorial: já o dividimos em problemas menores a serem resolvidos. Agora falta só: resolvê-los!
Chegando ao caso base podemos começar a resolver os casos do menor para o maior problema.
Sabemos que o caso base do nosso problema é quando o fatorial for 0.
E o que acontece quando chegarmos ao zero? Podemos retornar 1, pois 0! equivale a 1 e é o menor fatorial possível.
Relembrando também que um número fatorial é o seu próprio valor vezes o mesmo menos um.
Então para resolver o caso 1!, temos:
1! = 1 x 0!Se o caso base 0! = 1, podemos fazer:
1! = 1 x 11! = 1
A mesma ideia vale para 2!
2! = 2 x 1!Já resolvemos o problema do 1! , e sabemos que 1!= 1, logo:
2! = 2 x 12! = 2
De novo, para 3!:
3! = 3 x 2!3! = 3 x 23! = 6
Por fim, 4!:
4! = 4 x 3!4! = 4 x 64! = 24
Nas explicações e imagem acima, podemos identificar os passos para resolução do problema:
- Quebre o problema maior em subproblemas, até chegar ao caso base;
- Identifique o caso base (o caso base nesse caso é o fatorial de 0 que é igual a 1)
- A partir do caso base, comece a resolver os subproblemas um a um;
- Por fim, resolva o problema maior.
Esta é exatamente a forma recursiva de se pensar em um problema: dividimos-os em fatoriais menores até chegar ao caso base (quando chegar no fatorial de zero) e resolvendo do menor subproblema (fatorial de zero) até chegar no maior.
Abaixo segue um exemplo de um programa em Python resolvendo exatamente o problema acima utilizando recursão.
Como a melhor de maneira aprender é fazendo, fica um desafio para você:
Tente ser o “debugador” do programa (similar ao que fizemos na seção Apêndice: Pilha de Chamada) e execute o código passo a passo (com papel e lápis mesmo!), de acordo com a execução do fatorial.
Com isso, certamente você entenderá melhor o processo de recursão completo e verá que a pilha de chamada ficará parecida com todos os diagramas que vimos até aqui.
Conclusão
A recursão utilizando a estratégia de dividir e conquistar é algo crucial para entender como alguns dos principais algoritmos computacionais funcionam.
Por meio dos exemplos, podemos entender que para utilizar recursão precisamos:
- Ter um caso base (implícito ou explícito);
- Quebrar em problemas menores;
- Resolver cada subproblema;
- Com a solução dos subproblemas, resolver o problema maior.
A ideia de dividir e conquistar e a recursão estão presentes em muitos dos principais algoritmos computacionais. Então para entendê-los, é preciso estar familiarizado de como essas ideias funcionam.
Vale citar também que em algumas linguagens puramente funcionais, não é possível utilizar iteração (ou seja, a utilização da instrução for ou while), sendo necessário utilizar recursão para fazer um processo equivalente.
Apêndice: Pilha de Chamada (Call Stack)
Trata-se de uma estrutura de dados LIFO (Last In First Out: último a entrar, primeiro a sair) o qual compreenderemos melhor seu funcionamento a seguir.
Não é o foco desse post explicar como essa estrutura de dados funciona na prática, mas se houver a curiosidade, segue abaixo um exemplo de implementação bem simples.
https://gist.github.com/henriquebraga/ca5a816c8292554bdcc5c7d88d37c889
A ideia dela é a mesma de uma pilha de pratos: quando queremos inserir um novo prato, colocamos no topo e se quisermos remover, tiramos do topo também (ou seja, o último que colocamos).
Todo programa quando é executado e carregado em memória, possui uma pilha de chamada.
Ela é vital para o funcionamento do programa, pois mantém todo o gerenciamento de todo o fluxo e controle de qual subrotina (função) deve-se ser executada.
Mas como assim?
Vamos entender melhor em um programa simples.
Todo programa precisa ter uma pilha de chamada. Considere o código a seguir:
Vamos entender passo a passo o que está acontecendo. Neste exemplo, podemos ignorar a função print() nativa do Python.
A primeira função a ser chamada em nosso programa é a função calcular() .
Então, colocamos a função calcular() no topo da pilha (push).
Seguindo na primeira linha da função calcular, temos a atribuição da variável res_soma ao resultado da função somar() executada, passando os parâmetros 1 e 2 respectivamente.
Porém, ao chamar a função somar(), não podemos de forma alguma perder da memória as informações sobre esta função, pois após a execução da mesma, o programa irá retornar para a linha de código de onde parou e continuar a execução da função calcular().
Para isso, ela ficará com estado pausado, conhecido também como parcialmente completa.
Então, o que será feito?
- A função calcular() será pausada e o seu estado salvo em memória.
- Colocamos a função somar(1,2) no topo da pilha!
Observação: A título de curiosidade, também é enviado o endereço de memória da função calcular(), assim quando terminar a execução da função somar(), ela saberá devolver o controle de execução para a função que estava no topo da pilha).
Agora, no metódo somar(1,2), os parâmetros 1 e 2 são representados pelas variáveis a e b respectivamente.
Note que temos o seguinte código:
A execução de instruções na linha de um programa geralmente é da direita para a esquerda. Então, precisamos resolver a expressão a + b.
Observação: Não vou entrar em detalhes do que acontece no Python, mas as variáveis a e b são objetos do tipo int e implementam o método especial __add__ , que sobrescreve o operador +, logo isso ocasiona mais uma chamada na pilha).
Ao resolver essa expressão, temos o valor 3.
Agora temos:
Como podemos observar, falta apenas executar a instrução return. Na maioria das linguagens de programação, esta significa que a execução do método termina naquele ponto, devolvendo a variável ou valor da expressão e o controle de execução para função logo abaixo dela, ou seja: calcular().
Também temos que removê-la (pop)da pilha de chamada.
Voltando a execução do método calcular().
A próxima instrução a ser resolvida pelo programa é a atribuição que está sendo feita. Como devolvemos o valor 3, temos:
A próxima etapa linha, temos uma instrução return, seguido de uma chamada para a função multiplicar(), passando os parâmetros da variável res_soma (3) e 2. Neste caso, antes da execução do return, fazemos aquele processo novamente:
- Pausamos a função calcular()
- Colocamos a função multiplicar(3 , 2) no topo da pilha
A função multiplicar(3, 2), basicamente temos o mesmo comportamento da função somar:
- Resolvemos as expressões mais à direita do return;
- A expressão mais à direita é: a(3) * b(2) (O Python assim como na soma, chama o método especial __mul__ que é chamado quando utilizamos o operador *)
- A expressão é resolvida (6) e a instrução return é executada;
- Removemos a função multiplicar(3, 2) e devolvemos o controle para função calcular(), juntamente como o valor da expressão resolvida (6)
Por fim, temos a última linha a instrução de retorno do nosso método calcular()
Agora que você já entendeu o fundamental sobre o funcionamento de uma pilha de chamada, vamos voltar no ponto que paramos sobre recursão.
