O que realmente é um algoritmo recursivo?

Indo direto ao ponto, um algoritmo recursivo, é aquele que invoca à 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áculo 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 quisessemos calcular o fatorial de 4, precisariamos antes saber o valor do fatorial de 3 e assim por diante.

Recursividade na computação

Se você já tentou desenvolver o algoritmo do cáculo 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 primeria coisa que irá acontecer vai ser mandarmos esse algoritmo para nossa pilha.

Para isto funcionar corretamente e ter suas próprias variaveis 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 seguirmos o mesmo processo para os demais números, ao final nossa pilha estará da sequinte 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áculo, 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 multiplas pendêcias, 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 cascatiadas 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 multiplas pendências e o retorno dos resultados dessas multiplas 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 fariamos 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 (esta que 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 multiplacado 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 uma estrutura 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-se que 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.

Obrigado! : )