Indo direto ao ponto, um algoritmo recursivo, é aquele que invoca a ele mesmo durante o processo de execução. Mas, será que é só isso?
Neste artigo quero te mostrar, de uma maneira simples, como este tipo de algoritmo realmente se comporta.
O que é a recursão?
Bem, quando estamos falando de ciência da computação, a recursividade é uma sub-rotina que se invoca durante o processo de execução de um programa.
Este tipo de algoritmo pode ser extremamente poderoso em alguns cenários, mas em outros nem tanto, podendo ser considerado até ineficiente.
Um exemplo muito claro do que é a recursão, é quando estudamos na matemática o cálculo do fatorial de um número qualquer. Exemplo:
factorial(1)= 1
factorial(2)= 2 * 1
factorial(3)= 3 * 2 * 1
factorial(4) = 4 * 3 * 2 * 1
Se pararmos para analisar, a fórmula para este processo sempre será a seguinte:
factorial(n) = n * factorial(n-1)
Vemos que a função chama à ela mesma, mas agora passando o valor de n – 1,para poder calcular o valor do fatorial de n.
Logo, se quiséssemos calcular o fatorial de 4, precisaríamos antes saber o valor do fatorial de 3 e assim por diante.
Recursividade e algoritmo recursivo na computação
Se você já tentou desenvolver o algoritmo do cálculo do fatorial de um número em uma determinada linguagem de programação, você pode ter percebido que não necessariamente existe apenas uma maneira de desenvolver esse algoritmo.
Mas sim por dois caminhos, um de maneira recursiva e outro de maneira iterativa. Então,qual vai ser a diferença entre os dois para o computador?
Primeiro,vamos discutir como esse algoritmo se comportaria de maneira recursiva:
int factorial (int n) {
if (n == 1) return 1;
else
return n * factorial(n-1);
}
Conforme vemos acima, quando retornamos a chamada da função factorial(n),estamos voltando para o mesmo pedaço de código.
Logo,chamamos o parâmetro n diversas vezes, mas em todas n sempre será diferente. Então teremos que manusear e separar esse parâmetro toda vez que chamarmos a função.
Assim, o que você precisa entender é que num algoritmo como este, não temos apenas um n como parâmetro sendo armazenado na memória. E para podermos manusear e separar apropriadamente, precisamos então de uma Stack.
Imagine que vamos calcular o fatorial do número 4. A primeira coisa que irá acontecer vai ser mandarmos esse algoritmo para nossa pilha.
Para isto funcionar corretamente e ter suas próprias variáveis locais, o que inclui todas as diferentes instâncias de n, nós mandamos outro frame para uma outra área da nossa pilha, que será a resposta do fatorial de 4.
Mas o fatorial de 4 exige que tenhamos o resultado do fatorial de 3, caso contrário não é possível obter o valor de 4.
Se seguirmoso mesmo processo para os demais números, ao final nossa pilha estará daseguinte maneira:
Agora,sabemos que o fatorial de 1 é ele mesmo, então o fatorial de 2 que estava aguardando o resultado pode prosseguir com o cálculo, retornando o valor do fatorial de 2 podemos prosseguir com o cálculo do fatorial de 3, e assim por diante, até chegarmos no programa principal com o resultado do fatorial de 4,que corresponde ao número 24.
O que percebemos, é que nessa sequência de múltiplas pendências, cada uma dessas está associada a um valor diferente de n. Então quando resolvemos o fatorial de 1, as respostas começam a ser cascateadas para as demais funções que estavam aguardando na Stack.
O fluxo do comportamento dessa função está logo abaixo:
(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
Se notarmos,podemos ver que o fluxo tem um comportamento gráfico de “ida e volta”,ou seja, temos as múltiplas pendências e o retorno dos resultados dessas múltiplas pendências.
Isto está relacionado com a necessidade de memória, pois a medida que vamos fazendo novas chamadas, e aguardamos o retorno dessas chamadas para continuar a computação,precisamos fazer empilhamentos na Stack, conforme vimos anteriormente.
Agora como faríamos esse algoritmo de maneira iterativa? Vamos ver no código abaixo:
int factorial (int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result = i * result;
}
}
O que fizemos aqui foi primeiro criar uma variável que inicia com o valor de 1 (estaque representa nosso resultado final) e depois criar um loop que a cada volta nós armazenamos na nossa variável result o valor do contador multiplicado pelo valor dela mesma. Ao final do algoritmo é retornado o valor da variável result, que no caso é o nosso resultado.
Com este tipo de procedimento, nós não temos a necessidade de “ir e voltar”, pois não tem computação sendo executada no retorno do processo. Logo, não temos necessidade de voltar todo o empilhamento feito na Stack.
Recursão em Árvore
A recursão em árvore, é um outro tipo de shape de execução que encontramos em alguns algoritmos recursivos. Ela é muita conhecida por seu fluxo ser moldado em umaestrutura de árvore.
Para exemplificar, vamos utilizar um algoritmo que nos retorna um número que pertence à sequência de Fibonacci e está na posição correspondente ao valor do nosso parâmetro:
int fibonacci (int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n – 1) + fibonacci(n – 2);
}
Se tentarmos executar este código passando o parâmetro como valor 5, a nossa função nos retornará o número 5 pois ele é o quinto número da sequência de Fibonacci (lembrando que começamos a contar do 0):
Sequência de Fibonacci
Logo, seu shape de execução terá o seguinte formato:
Por mais que isso seja interessante e nosso código no final fique enxuto e simples, uma abordagem como esta é ineficiente, pois se você reparar na imagem, verá que temos diversos galhos de execução repetidos, como por exemplo o fibonacci do número 1 (fib 1), o que acarreta um desperdício e compromete o tempo de execução do nosso algoritmo.
É importante tentarmos migrar um shape em árvore como este, para uma abordagem mais econômica. Neste caso, vamos utilizar um loop para termos um shape de execução iterativo:
int fibonacci(int n) {
int x = 0;
int y = 1;
int res = 0;
for (int i = 0; i <= n; i++) {
res = x;
x = y;
y = res + y;
}
return res;
}
A recursão em árvore não é sempre ruim, em alguns cenários ela é até necessária, por exemplo em file system de sistemas operacionais. Mas o interessante é como podemos prever os processos que estão sendo gerados à partir de seus procedimentos.
Conclusão
Espero que após você ter lido este artigo eu tenha te ajudado a entender um pouco mais sobre recursividade e como ela se comporta no processo de execução de algoritmos que utilizam desse tipo de estrutura.
Lembre-seque o fato do seu código estar enxuto e simples não significa que ele está eficiente, então sempre é bom entender a complexidade dos algoritmos que você está escrevendo para não causar desperdício na hora da execução.
Gostou das dicas? Agora complemente seu aprendizado com nosso artigo sobre o que é algoritmo e para que serve!
